Exploration-Exploitation Tradeoff

Overview

The field studies how a learner can discover which actions, options, or regions are valuable while still making use of what it has learned, in settings such as bandits, reinforcement learning, recommendation, and robotics. Common approaches include upper confidence bounds and Thompson sampling, randomized perturbations, Bayesian acquisition rules, and structured strategies such as explore-then-commit or coverage-driven planning. Regret guarantees are well developed for many bandit settings, but real tasks often add contextual information, partial feedback, changing environments, or limited trials. A central tension is that strategies that maximize immediate reward may gather too little information, while exploration that improves coverage or final decisions can cost short-term reward and may need to account for uncertainty, safety, and user or task differences.

Latest papers

62 papers2 papers in the last four weeks, down 82% on the four weeks before. 0.0% of all new papers.

Oct 28, 2025

Self-Concordant Perturbations for Linear Bandits

We consider the adversarial linear bandits setting and present a unified algorithmic framework that bridges Follow-the-Regularized-Leader (FTRL) and Follow-the-Perturbed-Leader (FTPL) methods, extending the known connection between them from the full-information setting. Within this framework, we introduce self-concordant perturbations, a family of probability distributions that mirror the role of self-concordant barriers previously employed in the FTRL-based SCRiBLe algorithm. Using this idea, we design a novel FTPL-based algorithm that combines self-concordant regularization with efficient stochastic exploration. Our approach achieves a regret of O(dnln⁡n)\mathcal{O}(d\sqrt{n \ln n}) on both the dd-dimensional hypercube and the ℓ2\ell_2 ball. On the ℓ2\ell_2 ball, this matches the rate attained by SCRiBLe. For the hypercube, this represents a d\sqrt{d} improvement over these methods and matches the optimal bound up to logarithmic factors.
Feb 24, 2025

Linear Bandits on Ellipsoids: Minimax Optimal Algorithms

We consider linear stochastic bandits where the set of actions is an ellipsoid. We provide the first known minimax optimal algorithm for this problem. We first derive a novel information-theoretic lower bound on the regret of any algorithm, which must be at least Ω(min⁡(dσT+d∥θ∥A,∥θ∥AT))Ω(\min(d σ\sqrt{T} + d \|θ\|_{A}, \|θ\|_{A} T)) where dd is the dimension, TT the time horizon, σ2σ^2 the noise variance, AA a matrix defining the set of actions and θθ the vector of unknown parameters. We then provide an algorithm whose regret matches this bound to a multiplicative universal constant. The algorithm is non-classical in the sense that it is not optimistic, and it is not a sampling algorithm. The main idea is to combine a novel sequential procedure to estimate ∥θ∥\|θ\|, followed by an explore-and-commit strategy informed by this estimate. The algorithm is highly computationally efficient, and a run requires only time O(dT+d2log⁡(T/d)+d3)O(dT + d^2 \log(T/d) + d^3) and memory O(d2)O(d^2), in contrast with known optimistic algorithms, which are not implementable in polynomial time. We go beyond minimax optimality and show that our algorithm is locally asymptotically minimax optimal, a much stronger notion of optimality. We further provide numerical experiments to illustrate our theoretical findings.