An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction

• URL: http://arxiv.org/abs/2508.11931v1
• Date: Sat, 16 Aug 2025 06:25:18 GMT
• Title: An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction
• Authors: Tim van Erven, Jack Mayo, Julia Olkhovskaya, Chen-Yu Wei,
• Abstract summary: We present an efficient algorithm for linear contextual bandits with adversarial losses and action sets.<n>Our algorithm is the first to achieve $text(d)sqrtT$ regret in time, while no prior algorithm achieves even $o(T)$ regret in time to our knowledge.
• Score: 13.78877509090251
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present an efficient algorithm for linear contextual bandits with adversarial losses and stochastic action sets. Our approach reduces this setting to misspecification-robust adversarial linear bandits with fixed action sets. Without knowledge of the context distribution or access to a context simulator, the algorithm achieves $\tilde{O}(\min\{d^2\sqrt{T}, \sqrt{d^3T\log K}\})$ regret and runs in $\text{poly}(d,C,T)$ time, where $d$ is the feature dimension, $C$ is an upper bound on the number of linear constraints defining the action set in each round, $K$ is an upper bound on the number of actions in each round, and $T$ is number of rounds. This resolves the open question by Liu et al. (2023) on whether one can obtain $\text{poly}(d)\sqrt{T}$ regret in polynomial time independent of the number of actions. For the important class of combinatorial bandits with adversarial losses and stochastic action sets where the action sets can be described by a polynomial number of linear constraints, our algorithm is the first to achieve $\text{poly}(d)\sqrt{T}$ regret in polynomial time, while no prior algorithm achieves even $o(T)$ regret in polynomial time to our knowledge. When a simulator is available, the regret bound can be improved to $\tilde{O}(d\sqrt{L^\star})$, where $L^\star$ is the cumulative loss of the best policy.

Related papers

• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibria is a powerful and flexible framework at the heart of online learning and game theory.<n>We show that an efficient online algorithm incurs average $Phi$-regret at most $epsilon$ using $textpoly(d, k)/epsilon2$ rounds.<n>We also show nearly matching lower bounds in the online setting, thereby obtaining for the first time a family of deviations that captures the learnability of $Phi$-regret.
  arXiv  Detail & Related papers  (2025-02-25T19:08:26Z)
• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
  We study best-of-both-worlds algorithms for $K$-armed linear contextual bandits. Our algorithms deliver near-optimal regret bounds in both the adversarial and adversarial regimes.
  arXiv  Detail & Related papers  (2023-12-24T08:27:30Z)
• Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits [30.337826346496385]
  We consider the adversarial linear contextual bandit problem, where the loss vectors are selected fully adversarially and the per-round action set is drawn from a fixed distribution. Existing methods for this problem either require access to a simulator to generate free i.i.d. contexts, achieve a sub-optimal regret, or are computationally inefficient. We greatly improve these results by achieving a regret of $widetildeO(sqrtT)$ without a simulator, maintaining computational efficiency when the action set in each round is small.
  arXiv  Detail & Related papers  (2023-09-02T03:49:05Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  We consider a contextual bandit problem with $S$ contexts and $K$ actions. We give an algorithm that outputs an $epsilon$-optimal policy after using at most $widetilde O(r (S +K )/epsilon2)$ samples. In the regret setting, we give an algorithm whose cumulative regret up to time $T$ is bounded by $widetilde O(sqrtr3(S+K)T)$.
  arXiv  Detail & Related papers  (2023-06-22T17:20:30Z)
• First- and Second-Order Bounds for Adversarial Linear Contextual Bandits [22.367921675238318]
  We consider the adversarial linear contextual bandit setting, which allows for the loss functions associated with each of $K$ arms to change over time without restriction. Since $V_T$ or $L_T*$ may be significantly smaller than $T$, these improve over the worst-case regret whenever the environment is relatively benign.
  arXiv  Detail & Related papers  (2023-05-01T14:00:15Z)
• Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
  Policy regret is a well established notion of measuring the performance of an online learning algorithm against an adaptive adversary. We study restrictions on the adversary that enable efficient minimization of the emphcomplete policy regret We provide an algorithm that w.h.p a complete policy regret guarantee of $tildemathcalO(mKsqrtT)$, where the $tildemathcalO$ notation hides only logarithmic factors.
  arXiv  Detail & Related papers  (2022-04-24T03:10:27Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  We consider the problem of combining and learning over a set of adversarial algorithms with the goal of adaptively tracking the best one on the fly. The CORRAL of Agarwal et al. achieves this goal with a regret overhead of order $widetildeO(sqrtd S T)$ where $M$ is the number of base algorithms and $T$ is the time horizon. Motivated by this issue, we propose a new recipe to corral a larger band of bandit algorithms whose regret overhead has only emphlogarithmic dependence on $M$ as long
  arXiv  Detail & Related papers  (2022-02-12T21:55:44Z)
• On Submodular Contextual Bandits [92.45432756301231]
  We consider the problem of contextual bandits where actions are subsets of a ground set and mean rewards are modeled by an unknown monotone submodular function. We show that our algorithm efficiently randomizes around local optima of estimated functions according to the Inverse Gap Weighting strategy.
  arXiv  Detail & Related papers  (2021-12-03T21:42:33Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  We study a constrained contextual linear bandit setting, where the goal of the agent is to produce a sequence of policies. We propose an upper-confidence bound algorithm for this problem, called optimistic pessimistic linear bandit (OPLB)
  arXiv  Detail & Related papers  (2020-06-17T22:32:19Z)

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.