In sequential decision-making, the multi-armed bandit framework captures the fundamental trade-off between exploration (gathering information) and exploitation (maximizing reward). In its classical formulation, every action costs the same, and the feedback is a simple scalar reward. However, real-world applications—ranging from clinical trials with varying financial costs to high-dimensional continuous control—shatter these simplistic assumptions.
To bridge this gap, a major research direction focuses on establishing minimax optimal regret bounds under resource constraints and complex action spaces. Minimax optimality guarantees that an algorithm performs as well as theoretically possible in the worst-case scenario. Rather than treating exploration as a uniform tax, modern optimal bandit frameworks achieve these bounds by exploiting two core principles: cost-proportional exploration and geometric gradient estimation.
Cost-Proportional Exploration under Finite Budgets
When pulling an arm incurs a financial or resource cost, standard exploration strategies like Upper Confidence Bound (UCB) or Thompson Sampling fail because they treat all information as equally cheap. If an informative arm is prohibitively expensive, a naive algorithm will quickly deplete its budget.
To solve this, budget-constrained frameworks maximize cumulative rewards or identify the best action before a total budget $B$ is exhausted. Yingce Xia et al. in Thompson Sampling for Budgeted Multi-Armed Bandits demonstrated that posterior sampling can be adapted to budgeted environments, proving a logarithmic regret bound of $O(\ln B)$. This means that as the budget scales, the efficiency loss relative to an optimal oracle grows remarkably slowly. This logarithmic scaling holds true even when multiple actions are selected simultaneously, as shown by Yingce Xia et al. in Budgeted Multi-Armed Bandits with Multiple Plays and Claire Tomlin et al. in Budget-Constrained Multi-Armed Bandits With Multiple Plays. Furthermore, Alexander Luedtke et al. proved in Asymptotically optimal algorithms for budgeted multiple play bandits that variants of both KL-UCB and Thompson Sampling achieve asymptotic optimality in these multiple-play settings, matching the theoretical lower bounds.
The core intuition behind these bounds lies in balancing an arm's information gain against its unit cost. In Cost Aware Best Arm Identification, Kellen Kanarios et al. proved a fundamental principle: the optimal sampling frequency for an arm should be proportional to the inverse square root of its expected cost ($\sim 1/\sqrt{\text{cost}}$). Weighting exploration this way allows the algorithm to rapidly eliminate cheap, suboptimal options, preserving the precious budget for distinguishing between high-value, expensive alternatives. This cost-aware lower bound tracking is generalized by Chengshuai Shi et al. in Cost-Aware Optimal Pairwise Pure Exploration to minimize cumulative expenditure across diverse ranking tasks.
Even when the objective shifts from maximizing pure reward to finding a "good enough" solution under a cost subsidy, this tight coupling remains. Ishank Juneja et al. showed in Pairwise Elimination with Instance-Dependent Guarantees for Bandits with Cost Subsidy that algorithms can achieve logarithmic growth for both cost and quality regret simultaneously. Similarly, when multiple feedback channels coexist (such as absolute rewards and pairwise dueling feedback), Xuchuang Wang et al. demonstrated in Fusing Reward and Dueling Feedback in Stochastic Bandits that a learner can achieve a regret bound scaling with the minimum cost of the two feedback types per arm, ensuring the algorithm always defaults to the most efficient information source.
Simulating Gradients in Bandit Convex Optimization
Moving from discrete arms to continuous spaces introduces a different kind of information constraint. In Bandit Convex Optimization (BCO), the learner seeks to minimize a sequence of convex functions but can only observe a single noisy function value at the chosen point, rather than the full gradient vector.
Historically, it was unclear whether bandit feedback inherently degraded performance compared to full-gradient online learning. Alekh Agarwal et al. settled a core piece of this puzzle in Stochastic Convex Optimization with Bandit Feedback by establishing a square-root-of-time ($\sqrt{T}$) regret bound for convex functions, proving that these problems are fundamentally as efficient to solve as linear ones. Sebastien Bubeck et al. solidified this in Bandit Convex Optimization: (\sqrt{T}) Regret in One Dimension, proving that the minimax regret for one-dimensional BCO is precisely $\Theta(\sqrt{T})$.
How do we achieve $\sqrt{T}$ regret without gradients? The mechanism relies on randomized gradient estimation via shrinking exploration. To estimate a gradient at a point, an algorithm "pokes" the function by sampling randomly within a small sphere of radius $\delta$ around that point. By applying Stokes' theorem, the observed scalar value can be transformed into an unbiased estimate of the gradient of a smoothed version of the function.
However, a large exploration radius $\delta$ introduces high bias (since we are optimizing a smoothed function, not the true one), while a tiny $\delta$ explodes the variance of our gradient estimate. To achieve minimax optimality, the exploration must shrink over time. Elad Hazan et al. leveraged this in Bandit Convex Optimization: Towards Tight Bounds, showing that for strongly convex and smooth loss functions, one can achieve a near-optimal $\tilde{O}(\sqrt{T})$ regret by using the geometry of self-concordant barriers to systematically shrink the exploration zone. Shinji Ito advanced this in An Optimal Algorithm for Bandit Convex Optimization with Strongly-Convex and Smooth Loss, matching the theoretical minimax optimal bound of $O(d\sqrt{T})$ using a simpler membership oracle that eliminates the need for complex barrier constructions entirely.
Geometric Foundations of Optimal Exploration
The challenge of continuous exploration becomes acute when the action space has complex geometric boundaries or structural bottlenecks. To maintain minimax optimality, algorithms must choose their exploration directions based on the underlying geometry of the space.
In Volumetric Spanners: An Efficient Exploration Basis for Learning, Elad Hazan et al. introduced volumetric spanners—a geometric tool that finds a set of well-aligned basis vectors within any arbitrary convex set. By exploring along the axes of this volumetric spanner, an algorithm ensures that it learns about all dimensions of the action space without stepping outside the feasible region or wasting samples on redundant directions. This yielded the first efficient, near-optimal regret algorithm for linear optimization over general convex sets.
This geometric perspective also clarifies why randomized algorithms like Thompson Sampling work well in continuous or smooth settings. Marc Abeille et al. in Linear Thompson Sampling Revisited. provided a frequentist proof showing that Thompson Sampling's regret is directly tied to the gradient of the objective function at an optimistic parameter estimate. This geometric link bypasses complex variance tracking, proving that any distribution with a constant probability of being optimistic can achieve optimal regret. When the underlying reward functions are infinitely smooth, James A. Grant et al. demonstrated in On Thompson Sampling for Smoother-than-Lipschitz Bandits that Thompson Sampling naturally achieves the gold-standard $O(\sqrt{T})$ regret rate by exploiting the low eluder dimension of smooth functions.
Finally, when high-dimensional continuous spaces are constrained by a scalar bottleneck, Aadirupa Saha et al. showed in Optimal regret algorithm for Pseudo-1d Bandit Convex Optimization that a hybrid strategy combining kernelized exponential weights with structured gradient descent achieves a tight minimax optimal regret bound of $\min(\sqrt{dT}, T^{3/4})$, proving that structural bottlenecks can be explicitly leveraged to beat general-purpose bandit bounds.
Historically, algorithms often had to choose between being minimax optimal (robust across all problem difficulties) or asymptotically optimal (perfect in the long run for a specific instance). Pierre MENARD et al. reconciled this in A minimax and asymptotically optimal algorithm for stochastic bandits by introducing the $\text{kl-UCB}^{++}$ algorithm, proving that a single geometric framework can simultaneously satisfy both tight bounds. Whether an algorithm is scaling its sampling frequency inversely with the square root of financial costs, or shrinking its geometric exploration radius along a volumetric spanner to simulate gradients, optimality is achieved by aligning the search pattern with the underlying constraints of the environment.
Key Foundational Work
Online convex optimization in the bandit setting: gradient descent without a gradient (2005) — contributed 1 concept elements to this direction.
Stochastic Convex Optimization with Bandit Feedback (2013) — contributed 1 concept elements to this direction.