Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs

• URL: http://arxiv.org/abs/2205.09056v3
• Date: Sun, 10 Mar 2024 02:52:58 GMT
• Title: Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs
• Authors: Ian A. Kash, Lev Reyzin and Zishun Yu
• Abstract summary: Reinforcement learning generalizes multi-armed bandit problems with additional difficulties of a longer planning horizon and unknown transition kernel. We show that any slowly changing adversarial bandit algorithm achieving optimal regret in the adversarial bandit setting can also attain optimal expected regret in infinite-horizon discounted Markov decision processes.
• Score: 10.68896183306706
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Reinforcement learning generalizes multi-armed bandit problems with additional difficulties of a longer planning horizon and unknown transition kernel. We explore a black-box reduction from discounted infinite-horizon tabular reinforcement learning to multi-armed bandits, where, specifically, an independent bandit learner is placed in each state. We show that, under ergodicity and fast mixing assumptions, any slowly changing adversarial bandit algorithm achieving optimal regret in the adversarial bandit setting can also attain optimal expected regret in infinite-horizon discounted Markov decision processes, with respect to the number of rounds $T$. Furthermore, we examine our reduction using a specific instance of the exponential-weight algorithm.

Related papers

• An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints [29.596684377841182]
  In this study, we consider the infinitely many-armed bandit problems in a rested rotting setting, where the mean reward of an arm may decrease with each pull, while otherwise, it remains unchanged. We introduce an algorithm that utilizes UCB with an adaptive sliding window, designed to manage the bias and variance trade-off arising due to rotting rewards.
  arXiv  Detail & Related papers  (2024-04-22T14:11:54Z)
• Multi-Armed Bandits with Abstention [62.749500564313834]
  We introduce a novel extension of the canonical multi-armed bandit problem that incorporates an additional strategic element: abstention. In this enhanced framework, the agent is not only tasked with selecting an arm at each time step, but also has the option to abstain from accepting the instantaneous reward before observing it.
  arXiv  Detail & Related papers  (2024-02-23T06:27:12Z)
• Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When Partial Feedback Counts [53.579515853222986]
  We study a novel bandit setting, namely Multi-Armed Bandit with Temporally-Partitioned Rewards (TP-MAB) This setting is a natural extension of delayed-feedback bandits to the case in which rewards may be dilated over a finite-time span after the pull. We provide two algorithms to address TP-MAB problems, namely, TP-UCB-FR and TP-UCB-EW.
  arXiv  Detail & Related papers  (2022-06-01T15:56:59Z)
• Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences [28.79598714109439]
  We study the problem of $K$-armed dueling bandit for both and adversarial environments. We first propose a novel reduction from any (general) dueling bandits to multi-armed bandits. Our algorithm is also the first to achieve an optimal $O(sum_i = 1K fraclog TDelta_i)$ regret bound against the Condorcet-winner benchmark.
  arXiv  Detail & Related papers  (2022-02-14T13:37:23Z)
• Bias-Robust Bayesian Optimization via Dueling Bandit [57.82422045437126]
  We consider Bayesian optimization in settings where observations can be adversarially biased. We propose a novel approach for dueling bandits based on information-directed sampling (IDS) Thereby, we obtain the first efficient kernelized algorithm for dueling bandits that comes with cumulative regret guarantees.
  arXiv  Detail & Related papers  (2021-05-25T10:08:41Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  We study a novel variant of online finite-horizon Markov Decision Processes with adversarially changing loss functions and initially unknown dynamics. In each episode, the learner suffers the loss accumulated along the trajectory realized by the policy chosen for the episode, and observes aggregate bandit feedback. Our main result is a computationally efficient algorithm with $O(sqrtK)$ regret for this setting, where $K$ is the number of episodes.
  arXiv  Detail & Related papers  (2021-01-31T16:49:07Z)
• Lifelong Learning in Multi-Armed Bandits [22.301793734117805]
  We study the problem in the multi-armed bandit framework with the objective to minimize the total regret incurred over a series of tasks. While most bandit algorithms are designed to have a low worst-case regret, we examine here the average regret over bandit instances drawn from some prior distribution which may change over time.
  arXiv  Detail & Related papers  (2020-12-28T15:13:31Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  We provide a simple method to combine bandit algorithms. Our approach is based on a "meta-UCB" procedure that treats each of $N$ individual bandit algorithms as arms in a higher-level $N$-armed bandit problem.
  arXiv  Detail & Related papers  (2020-12-24T05:36:29Z)
• A Novel Confidence-Based Algorithm for Structured Bandits [129.30402124516507]
  We study finite-armed bandits where the rewards of each arm might be correlated to those of other arms. We introduce a novel phased algorithm that exploits the given structure to build confidence sets over the parameters of the true bandit problem.
  arXiv  Detail & Related papers  (2020-05-23T19:52:44Z)
• Bandit algorithms to emulate human decision making using probabilistic distortions [20.422725678982726]
  We formulate two sample multi-armed bandit problems with distorted probabilities on the reward distributions. We consider the aforementioned problems in the regret minimization as well as best arm identification framework for multi-armed bandits.
  arXiv  Detail & Related papers  (2016-11-30T17:37:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.