A Tight Lower Bound and Efficient Reduction for Swap Regret
Authors: Shinji Ito
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper shows an (p TN log N)-lower bound for swap regret, where T and N denote the numbers of time steps and available actions, respectively. Our lower bound is tight up to a constant, and resolves an open problem mentioned, e.g., in the book by Nisan et al. [28]. Besides, we present a computationally efficient reduction method that converts no-external-regret algorithms to no-swap-regret algorithms.This study’s contribution is two-fold: one is a tight lower bound for swap regret, and the other is a novel efficient method for achieving no-swap-regret. The first result can be summarized in the following theorem: Theorem 1. ... A constructive proof of this theorem is given in Section 5. |
| Researcher Affiliation | Industry | Shinji Ito NEC Corporation i-shinji@nec.com |
| Pseudocode | Yes | Algorithm 1 Reduction from external to swap regret |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described in this paper. There are no explicit statements of code release or links to a repository. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments on a specific dataset. Therefore, no information about publicly available or open datasets for training is provided. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments with datasets, thus it does not provide specific dataset split information for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments that would require specific hardware. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe experiments or implementations that would require specific ancillary software details with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe experiments; therefore, it does not provide specific experimental setup details such as concrete hyperparameter values or training configurations. |