Bandit Algorithms

By Tor Lattimore, Csaba Szepesvari. 2020

sets of environments and policies respectively and ` : E ×Π→ [0, 1] a bounded loss function. Given a policy π let `(π) = (`(ν1, π), . . . , `(νN , π)) be the loss vector resulting from policy π. Define S = {`(π) : π ∈ Π} and λ(S) = {x ∈ cl(S) : y 6< x for all y ∈ S} , where y 6< x is defined to mean it is not true that yi ≤ xi for all i with strict inequality for at least one i. Prove that if λ(S) ⊆ S and S is convex, then for each x ∈ λ(S) there exists a prior q ∈ P(E) and policy π∗ such that `(π) = x and ∑ ν∈E q(ν)`(ν, π∗) = min π∈Π ∑

Subfields: Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Reinforcement Learning

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “Importantly, the regret scales nearly optimally with d √ T dependency given existing Ω(d √ T ) lower bounds for linear bandits (Lattimore and Szepesvári, 2020) and known reductions between the standard and preference regret Saha (2021).”
Degenerate Feedback Loops in Recommender Systems (2019, methodology): “We see that the Optimal Oracle results in the fastest degeneration by far, followed by the Oracle, TS and UCB .”
Neural Contextual Bandits with UCB-based Exploration (2019, background): “The stochastic contextual bandit problem has been extensively studied in machine learning [13, 5, 14]: at round t ∈ {1, 2, .”
Reactive Exploration to Cope with Non-Stationarity in Lifelong Reinforcement Learning (2022, methodology): “…take a Bayesian approach and investigate Thompson sampling and its relation to non-stationarity, Wu et al. (2018) propose a contextual bandit (Lattimore & Szepesvári, 2020) algorithm to detect changes based on its reward estimation confidence, and update the bandit arm selection strategy…”
Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL (2020, methodology): “As a clarifying example, consider choosing a sampling distribution µ according to globally-optimal design of experiments (Pukelsheim, 2006), which is an optimal procedure in linear bandits to recover the unknown parameter ( Lattimore & Szepesv´ari, 2020).”
Provably Efficient Reinforcement Learning with Linear Function Approximation (2019, background): “See [12, 25] and the references therein for a detailed survey.”
Stochastic matrix games with bandit feedback (2020, background): “Carefully controlling how the bounds change over time yield algorithms that achieve low regret [11, 23].”
Introduction to Multi-Armed Bandits (2019, background): “An excellent book on multi-armed bandits, Lattimore and Szepesvári (2019), will appear later this year.”
Is Pessimism Provably Efficient for Offline RL? (2020, background): “In comparison with online RL (Lattimore and Szepesv´ari, 2020; Agarwal et al., 2020a), ofﬂine RL remains even less understood in theory (Lange et al., 2012; Levine et al., 2020), which hinders principled developments of trustworthy algorithms in practice.”
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium (2020, background): “In particular, our setting covers both tabular MDPs as well as the linear MDP setting considered in Jin et al. (2019).”
Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability (2021, methodology): “…as the proof of Thm. 5 along with applying the standard concentration techniques from the linear bandits literature with proper tuning of λ and η (see Y. Abbasi-Yadkori and Szepesvari [2011]; Li et al. [2017]; Lattimore and Szepesvári [2020] for details on concentration results of linear ban-dits).”
The Importance of Pessimism in Fixed-Dataset Policy Optimization (2020, background): “to find a policy with high return. as it is analogous to the widely-known optimism principle [22] of exploration. µ gives the true mean of each action. n D the pulls used to construct dataset D , and µ D”
Model-Based Reinforcement Learning with Value-Targeted Regression (2020, background): “Rusmevichientong & Tsitsiklis (2010) gave a regret lower bound of Ω(d √ T ) for linearly parameterized bandit with actions on the unit sphere (see also Section 24.2 of Lattimore & Szepesvári 2020).”
Improved Optimistic Algorithms for Logistic Bandits (2020, methodology): “…that they all depend in an “unpleasant manner on the form of the link function of the GLM, and it seems there may be signiﬁcant room for improvement” (Lattimore and Szepesv´ari, 2018, § 19.4.5). degree of More in detail, the regrets scale with a multiplicative factor κ which characterizes the…”
Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited (2020, methodology): “By analogy with the existing minimax regret bound for multi-armed bandits (Auer et al., 2002; Lattimore and Szepesvári, 2020), the regret lower bound should be Ω(H √ HAT ), by taking H = Θ(H).”
On the Theory of Reinforcement Learning with Once-per-Episode Feedback (2021, background): “The second part is a restatement of (Lattimore and Szepesvári, 2020, Lemma 19.4).”
Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism (2020, methodology): “The traditional stream of research (Auer et al., 2002a; Bubeck & Cesa-Bianchi, 2012; Lattimore & Szepesv´ari, 2018) on stochastic multi-armed bandits (MAB) focused on the interplay be-tween uncertainty and bandit feedback ( i.e. , challenges 3 and 4), and (Auer et al., 2002a) proposed the classical…”
Individual Fairness in Hindsight (2018, methodology): “Formally, we consider a general online decision-making problem under uncertainty that falls into the class of stochastic contextual bandit problems that have been well-studied in literature (see, for example, Section 5 of Lattimore and Szepesvári (2020) for an overview).”