Linear Bandit
A generalization of the multi-armed bandit problem in which, at each round, an action a_t is selected from an action set A subset of R^d and a reward r_t = <a_t, θ*> + η_t is observed, where θ* is an unknown parameter vector. Algorithms exploit the linear structure across actions to infer θ* from partial feedback.
Timeline (last 90 days)
IAFTRL (information-acquisition follow-the-regularized-leader) is claimed by the paper to be the first linear bandit algorithm that achieves both adversarial-optimal (~O(√T) regret) and stochastic instance-dependent optimal (~O(C* log T) regret) performance within a pure FTRL framework.
In finite-action-set linear bandit problems, the adversarial environment requires the algorithm to guarantee ~O(√T) regret, and the stochastic environment expects O(log T)-level regret.
Linear bandits are a generalization of the multi-armed bandit problem, whose reward model is r_t = ⟨a_t, θ*⟩ + η_t, where θ* is the unknown parameter vector and η_t is noise.
The paper currently focuses on linear bandits with finite action sets, and extension to infinite action sets or nonlinear models remains an open direction.
All Facts (4)
IAFTRL (information-acquisition follow-the-regularized-leader) is claimed by the paper to be the first linear bandit algorithm that achieves both adversarial-optimal (~O(√T) regret) and stochastic instance-dependent optimal (~O(C* log T) regret) performance within a pure FTRL framework.
50%UnverifiedIn finite-action-set linear bandit problems, the adversarial environment requires the algorithm to guarantee ~O(√T) regret, and the stochastic environment expects O(log T)-level regret.
50%UnverifiedLinear bandits are a generalization of the multi-armed bandit problem, whose reward model is r_t = ⟨a_t, θ*⟩ + η_t, where θ* is the unknown parameter vector and η_t is noise.
50%UnverifiedThe paper currently focuses on linear bandits with finite action sets, and extension to infinite action sets or nonlinear models remains an open direction.
50%