Linear Contextual Bandits

Follow this topic Ask about this topic

Momentum

2 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 17

All topics

Oct 5, 2026cs.LG

Sampling Allocation of LinUCB: Optimal Design Limits in the Small-Gap Regime

We study the sampling allocation of LinUCB in the small-gap regime, where the reward gaps are of order at most

n^{-1/2}

over the decision horizon

n

. This scaling captures the hard instances underlying worst-case regret lower bounds, for which LinUCB is known to be near optimal up to logarithmic factors in

n

. Using a mean-field perspective, we characterize this allocation through the empirical sampling distribution, a macroscopic object that averages the effect of adaptive decisions over the horizon, and identify its limit as

n\to\infty

. We establish that in this regime, the empirical sampling distribution induced by LinUCB converges to the set of D-optimal designs. This central result reveals that, in the small-gap regime, LinUCB not only achieves near optimal minimax regret but also allocates samples in a way that is asymptotically efficient for learning the reward parameter, thereby connecting regret-driven online learning with information-efficient experimental design. Building on the optimal design limit, we obtain two useful consequences. First, we refine the asymptotic regret analysis of LinUCB in the small-gap regime by characterizing its leading-order constant in the limit. Second, we show that, despite LinUCB's adaptive sampling strategy, the regularized least-squares estimator satisfies a central-limit-type theorem in the small-gap regime, thereby enabling valid statistical inference for the reward parameter.

Yujie Liu, Vincent Y. F. Tan, Yunbei Xu

National University of Singapore

Adaptive Inference Contextual Bandits UCB Algorithms Linear Contextual Bandits

Ask PDF

Sep 14, 2026cs.LG

Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets

We study stochastic linear contextual bandits with arbitrary action menus that may depend on the fixed parameter and the interaction history. We establish matching upper and lower bounds, up to logarithmic factors. Let

d

be the dimension,

K

be the menu size, and

T

the time horizon. For

2\le K\le d

, we prove an upper bound

\widetilde O(K^{1/4}\sqrt{dT})

. When

T\ge d^2

, we further prove a lower bound

Ω(K^{1/4}\sqrt{dT})

. Thus, for

T\ge d^2

and

2\le K\le d

, the upper and lower bounds match up to logarithmic factors, and the polynomial dependence on

K

is optimal. Compared with the previous

\widetilde O(\sqrt{dKT})

bound, our upper bound improves the dependence on

K

by a factor of

K^{1/4}

. For

K\ge d

, we prove an upper bound

\widetilde O_{d,T}\left(\sqrt{dT}\min\{\sqrt d,(d\log K)^{1/4}\}\right)

and a lower bound

Ω\left(\sqrt{dT}\min\left\{\sqrt d,\left(\frac{d\log K}{\log(2d)}\right)^{1/4}\right\}\right)

. Here,

\widetilde O_{d,T}

omits logarithmic factors only in

d

and

T

. In particular, for polynomially large

K\ge d

, the upper and lower bounds both scale as

d^{3/4}\sqrt T

up to logarithmic factors, improving the standard

\widetilde O(d\sqrt T)

rate by a factor of

d^{1/4}

. As

K

grows further, the regret smoothly recovers the

d\sqrt T

scale once

\log K

reaches order

d

Tianyuan Jin

Data Science and Analytics Thrust The Hong Kong University of Science and Technology (Guangzhou)

Multi-Armed Bandits Minimax Regret Contextual Bandits Linear Contextual Bandits

Ask PDF

Sep 9, 2026cs.LG

Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits

Meta-learning has emerged as an effective paradigm for transferring knowledge across sequential bandit tasks. While substantial progress has been made for stochastic bandits and non-contextual adversarial bandits, meta-learning for adversarial linear contextual bandits (ALCBs) with random action sets remains largely unexplored. To address this problem, we propose Meta-LinEXP3, an online-within-online algorithm that constructs a predictable task-level prior from completed tasks to guide the inner LinEXP3 learner. For known context distributions, we develop a policy-centered estimator that achieves an intrinsic-dimension

\mathcal{O}(\sqrt{n})

per-task regret bound. For unknown distributions, we introduce a past-only regularized moment estimator with an

\mathcal{O}(n^{2/3})

leading regret term and explicit finite-sample error. We further establish a direct connection between prior accuracy and transfer regret, showing that increasingly accurate priors yield sublinear transfer-dependent regret across tasks. Experiments demonstrate the effectiveness of Meta-LinEXP3, including its application to structured hyperspectral tensor sampling.

Hao Li, Jie Xu, Zheng Xie

College of Science, National University of Defense Technology, Changsha 410073, China

Multi-Armed Bandits Contextual Bandits Adversarial Bandits Linear Contextual Bandits

Ask PDF

Aug 11, 2026cs.LG

Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints

We study new algorithms for Contextual Bandits with Knapsack. In these problems, there are finitely many types of customers, products, and resources. Each product is made from a fixed combination of resources, and resources have finite capacity. A decision maker must assign each arriving customer one out of a set of multiple possible products. Every assignment of a customer to a product will generate a random reward, which equals an unknown linear function of customer and product features, plus a noise term. The objective is to jointly learn the mean reward function, and to make online assignments to minimize the expected revenue loss relative to an optimal policy that knows the reward function. We propose a natural and simple extension of the Upper-Confidence-Bound (UCB) family of algorithms and apply re-optimization techniques. We show that by taking advantage of re-optimization, our algorithm achieves an average regret of

O(\frac{(\ln T)^3}{T})

where

T

is the horizon length. Our bound significantly reduces the

O(\frac{1}{\sqrt{T}})

bound in the literature for closely related dynamic-pricing problems that are based on re-optimization.

Zhen Xu

Management School, University of Liverpool, Liverpool, United Kingdom

Contextual Bandits UCB Algorithms Linear Contextual Bandits

Ask PDF

Aug 7, 2026cs.CL

Progressive Content Refinement with Decaying Reward Joint LinUCB

Iterative refinement has significantly enhanced Large Language Model (LLM) performance; however, existing methods ranging from feedback-based Self-Refine to traditional bandit approaches often rely on static options or overlook the saturation effect. This neglect leads to over-exploitation, where the continuous use of identical prompts or arms results in diminishing rewards over time. To address this challenge, we propose a novel contextual bandit algorithm that explicitly incorporates reward decay modeling. Utilizing an Expectation-Maximization (EM) algorithm, our method simultaneously estimates both arm-specific and decay parameters. Furthermore, by embedding prompts as arms, we facilitate the joint learning of arm values, distinguishing our approach from the traditional disjoint Linear Upper Confidence Bound (LinUCB) framework. Experimental results on Sentiment Reversal and GSM8K benchmarks demonstrate that our method achieves significant performance gains over strong baselines. Finally, our ablation study confirms that the integration of reward decay modeling within the bandit framework is crucial for mitigating over-exploitation and optimizing the iterative refinement process.

Shion Ishikawa, Pablo Loyola, Young-joo Chung +1

Rakuten Group, Inc. Tokyo, Japan · Rakuten Group, Inc. San Mateo, USA

LLM Self-Refinement Large Language Model-Guided Optimization Non-Stationary Bandits Contextual Bandits Linear Contextual Bandits

Ask PDF

Jul 3, 2026cs.LG

Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions

Many online decision-making problems involve both round-specific feasible actions and drifting reward models: eligible ad impressions, feasible prices, and available treatments can change over time, while user preferences, demand curves, and patient responses may evolve. Motivated by these applications, we study non-stationary linear bandits with round-specific feasible decision sets. Existing methods that obtain the optimal

\widetilde O(T^{2/3}P_T^{1/3})

dependence, where

P_T

is the path length of the reward-parameter sequence, impose an orthogonal-structure assumption on round-specific decision sets, which can be restrictive in contextual applications. We address this gap through a unified misspecification-reduction viewpoint: after partitioning the horizon into blocks, we relate each block's dynamic regret to regret against a fixed-parameter linear bandit benchmark, with the within-block parameter drift entering as bounded misspecification. Restarting algorithms with misspecification-dependent regret guarantees then yields the optimal

T^{2/3}P_T^{1/3}

dynamic-regret dependence for both linear bandits with general compact decision sets and

K

-armed contextual linear bandits.

Zihao Hu, Yuan Yao, Jiheng Zhang +1

Department of Mathematics, The Hong Kong University of Science and Technology

Dynamic Regret Minimization Non-Stationary Bandits Contextual Bandits Linear Contextual Bandits

Ask PDF

Jun 26, 2026cs.LG

Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspaces

Contextual bandits with graph-structured arms arise in recommendation, citation retrieval, and social advertising, where arms connected on a graph tend to share reward signal. Standard dimensionality reduction ignores this structure, inflating exploration cost by a factor of

d/k

. We propose GraphDR-LinUCB, which projects arm features onto the graph's low-frequency spectral subspace and runs linear UCB in the resulting

k

-dimensional space. We prove the first

\wtO(k\sqrt{T})

regret bound for spectral-projection-based contextual bandits, reducing dimension dependence from

d

k

; a perturbation argument extends this to noisy graphs, with an explicit penalty for reward-smoothness mismatch and graph-estimation error. Our central theoretical finding is that the high-frequency reward component need not incur a worst-case linear-in-

T

penalty: its actual cost depends on its realized impact along the played path, not on its total energy. A simple spectral comparison between subspaces (

Γ_k

) predicts which reducer wins on a given dataset, correctly calling five of six real-dataset outcomes without any fitted threshold. Across a synthetic benchmark and six real datasets (MovieLens, Amazon, LastFM, ogbn-arxiv, MIND), GraphDR-LinUCB reduces cumulative regret by

15\times

over full-dimensional LinUCB and outperforms competing graph-aware methods on five of six; the single failure is precisely where the graph's spectral subspace is misaligned with the reward.

Joyanta Jyoti Mondal, Ibne Farabi Shihab, Anuj Sharma

Department of Computer and Information Sciences, University of Delaware, USA · Department of Computer Science, Iowa State University, USA · Department of Civil, Construction & Environmental Engineering, Iowa State University, USA

Multi-Armed Bandits Graph Bandits Contextual Bandits Dimensionality Reduction Linear Contextual Bandits

Ask PDF

Jun 22, 2026eess.SY

Flow-Corrected Thompson Sampling for Non-Stationary Contextual Bandits

We study non-stationary linear contextual bandits where the reward model drifts over time, rendering classical contextual bandit algorithms brittle because historical data becomes systematically biased. We propose Flow-Corrected Thompson Sampling (fcTS), a Bayesian method that reuses experience by transporting past rewards to the present using an explicit drift model and incorporating each transported observation with a confidence weight that reflects transport reliability. This yields a unified template that specializes in (i) linear parameter drift via online slope estimation and reward correction, (ii) periodic variation via phase-aware reuse across cycles, and (iii) recurring regime switches via changepoint detection and regime-specific posterior memory. The resulting posterior updates remain closed-form under a linear Gaussian model and can be implemented efficiently with truncated, incrementally updated sufficient statistics. Across five controlled case studies and a semi-synthetic portfolio-selection benchmark with multiple overlapping non-stationarities, fcTS outperforms standard forgetting-based baselines (discounting, sliding windows, and periodic restarts), with the largest gains in settings exhibiting recurring temporal structure. These results demonstrate that when non-stationarity is structured, correcting and reweighting historical observations can be substantially more sample-efficient than uniformly discarding them.

AmirHossein Naghdi, Ali Baheri

Sharif University of Technology, Iran · Rochester Institute of Technology, USA

Thompson Sampling Non-Stationary Bandits Contextual Bandits Linear Contextual Bandits

Ask PDF

Jun 18, 2026stat.ML

Stochastic Linear Contextual Bandits with Bounded Noise: A Set-Membership Approach

This paper considers stochastic linear contextual bandits (SLCB) with bounded reward noise. Existing works typically assume sub-Gaussian reward noise and bounded expected rewards, under which the optimal regret bound scales as

\tilde{O}(\sqrt{T})

in terms of horizon

T

. However, in many applications, realized/observed rewards are also naturally bounded, implying bounded reward noise. Bounded noise is more informative than the sub-Gaussian condition but has not been leveraged explicitly in the SLCB literature. In this paper, we propose a novel algorithm SME-OFU by utilizing an uncertainty quantification method called set-membership estimation (SME) and applying the principle of optimism in the face of uncertainty (OFU). Our algorithm enjoys an improved regret bound

O(\log T)

. Notice that this does not contradict the existing optimal bound

\tilde{O}(\sqrt{T})

for sub-Gaussian noise because bounded noise is a stronger condition. Finally, simulations show empirical improvements of SME-OFU over a benchmark algorithm designed for sub-Gaussian noise when the reward noise is bounded.

Haonan Xu, Yingying Li

The Grainger College of Engineering University of Illinois Urbana-Champaign Champaign, IL, 61801

Multi-Armed Bandits Contextual Bandits UCB Algorithms Linear Contextual Bandits

Ask PDF

Jun 8, 2026cs.LG

Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Drifts

We consider a variant of the linear contextual stochastic multi-armed bandits, where the learner must provide recommendations to a group of users, each having its personalized preference vector, and in the presence of context distributions that are drifting over time. Under practitioner-friendly assumptions, we reduce this setting to linear bandit with stationary mean but heteroskedastic and non-stationary noise. We further study the case when the learner must ensure the mean reward of each decision must exceed that of a baseline strategy

\boldsymbolπ_0

at each decision step. We introduce Dri-MED, an algorithm inspired from the linear version of the MED strategy, and carefully adapted to handle the non-stationary heteroskedastic noise. We show that the instance-dependent regret scales as

\tilde{\mathcal O}\left(\fracκ{\tildeΔ}d^2(\log(T)\right)

, where

\tildeΔ

is the constraint-aware sub-optimality gap subject to policy

π_0

, with variance-aware multiplicative term

κ

that we carefully handle using heteroskedastic regression. We further show Dri-MED enjoys

\tilde{\mathcal{O}}(d)

expected constraint violations. Our numerical results suggest that Dri-MED significantly outperforms conservative baselines that ignores the drift and preference structure.

Udvas Das, Waris Radji, Debabrota Basu +1

Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 – CRIStAL F-59000 Lille, France

Multi-Armed Bandits Non-Stationary Bandits Contextual Bandits Linear Contextual Bandits

Ask PDF

May 31, 2026stat.ML

Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates

We study linear contextual bandits under rare parameter updates: the learner may incorporate reward feedback into its parameter estimate only at a small number of update times, while still observing contexts online and selecting actions sequentially. This viewpoint clarifies a practical distinction that is often blurred in the literature: many "strictly batched" methods additionally restrict within-interval context adaptivity, meaning that the action rule inside an interval cannot depend on the sequence of realized contexts/actions in that interval (beyond the current round's context). For linear contextual bandits, we propose two practical algorithms with only

O(\log\log T)

parameter updates. Our first algorithm BLCE-G attains minimax-optimal regret (up to polylogarithmic factors in

T

) simultaneously in both the small-

K

and large-

K

regimes under a static schedule. Our second algorithm BLCE removes the near G-optimal design step -- a dominant computational bottleneck in prior strictly batched static-grid methods -- yet preserves minimax-optimal regret and achieves the lowest known runtime complexity among optimal algorithms. We further extend these rare-update and computational principles to generalized linear contextual bandits. Overall, our results yield statistically optimal algorithms under

O(\log\log T)

parameter updates that are also computationally efficient in practice.

Sanghoon Yu, Min-hwan Oh

Seoul National University, Seoul, Republic of Korea

Contextual Bandits Linear Contextual Bandits Generalized Linear Bandits

Ask PDF

May 24, 2026cs.LG

Active Learning for Stochastic Contextual Linear Bandits

A key goal in stochastic contextual linear bandits is to efficiently learn a near-optimal policy. Prior algorithms for this problem learn a policy by strategically sampling actions but naively (passively) sampling contexts from the underlying context distribution. However, in many practical scenarios -- including online content recommendation, survey research, and clinical trials -- practitioners can actively sample or recruit contexts based on prior knowledge of the context distribution. Despite this potential for active learning, the role of strategic context sampling in stochastic contextual linear bandits is underexplored. We propose an algorithm that learns a near-optimal policy by strategically sampling rewards of context-action pairs. We prove instance-dependent theoretical guarantees demonstrating that our active context sampling strategy can improve over the minimax rate by up to a factor of

\sqrt{d}

, where

d

is the linear dimension. We show empirically that our algorithm reduces the number of samples needed to learn a near-optimal policy, in tasks such as warfarin dose prediction and joke recommendation.

Emma Brunskill, Ishani Karmarkar, Zhaoqi Li

Stanford University

Active Learning Adaptive Sampling Contextual Bandits Policy Learning Linear Contextual Bandits

Ask PDF

May 18, 2026cs.LG

Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity

Many bandit deployments (recommendation, clinical dosing, ad targeting) share two facts prior work handles only in isolation: rewards live on a low-dimensional latent subspace, and that subspace drifts. Stationary low-rank bandits exploit rank but break under subspace change; non-stationary linear bandits adapt to drift but pay ambient rate

\widetilde{O}(d\sqrt{T})

. We study piecewise-stationary low-rank linear contextual bandits with scalar feedback:

θ_t = B_k^\star w_t

with rank-

r

factor

B_k^\star\in\mathbb{R}^{d\times r}

constant within each of

K

unknown segments and able to shift at boundaries. Our results are tight along three axes. (i) Identification boundary. With single-play scalar rewards, the moving subspace is recoverable through quadratic functionals of rewards iff three probe-side conditions hold: known noise variance, bounded state-noise coupling, and full-dimensional probe support. Each is necessary in the unrestricted-second-moment problem, and jointly they are sufficient, characterizing the boundary of the solvable region. (ii) Algorithm and dynamic regret. SPSC interleaves isotropic probes with windowed projected ridge-UCB exploitation inside the learned

r

-dimensional subspace; a CUSUM-style variant discovers segment boundaries online. The costed dynamic regret is

\widetilde{O}(r\sqrt{T})+\widetilde{O}(T^{2/3})+O(W\,V_{\mathrm{in}})

, replacing the ambient

d\sqrt{T}

rate with the intrinsic rank. (iii) Empirics. On eleven benchmarks spanning synthetic, UCI/MovieLens, semi-synthetic clinical, and ZOZOTOWN production-log data, SPSC outperforms non-stationary and low-rank baselines whenever

d-r\gtrsim T^{1/6}

, matching the analytical crossover. To our knowledge, this is the first work to characterize the identification boundary and attain the intrinsic-rank dynamic-regret rate in this setting.

Hamed Khosravi, Xiaoming Huo

H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332

Multi-Armed Bandits Non-Stationary Bandits Contextual Bandits Linear Contextual Bandits

Ask PDF

May 1, 2026cs.LG

Scaling Federated Linear Contextual Bandits via Sketching

In federated contextual linear bandits, high data dimensionality incurs prohibitive computation and communication costs: local agents perform

O(d^3)

-time determinant computation and upload

O(d^2)

parameters, making existing algorithms unscalable, where

d

is the dimension of data. To relieve these scaling bottlenecks, this paper proposes Federated Sketch Contextual Linear Bandits (FSCLB). On the computation side, FSCLB uses SVD to indirectly obtain the determinant required for communication, eliminating the prohibitive cost of direct determinant calculation and cutting complexity from

O(d^3)

O(l^2d)

per round, where

l< d

is the sketch size. On the communication side, FSCLB introduces a double-sketch strategy that reduces both upload and download costs from

O(d^2)

O(ld)

. Naively involving sketch update into federated contextual linear bandits can destroy the local increment and invalidate the asynchronous communication condition; FSCLB solves this by replacing the covariance matrix with the sketch matrix when deciding whether to communicate. Theoretically, FSCLB achieves a regret bound of

\widetilde{O} ((\sqrt{d}+\sqrt{M\varepsilon_l})\sqrt{lT})

, where

\varepsilon_l

is the upper bounded by the spectral tail of the covariance matrix; when

l

exceeds the rank of the covariance matrix, the bound simplifies to

\widetilde{O}(\sqrt{ldT})

, matching the optimal no-sketch regret. Experiments on both synthetic and real-world datasets show that FSCLB significantly reduces computational and communication costs by over 90 % while sacrificing only a negligible amount of cumulative reward.

Hantao Yang, Hong Xie, Xutong Liu +1

University of Science and Technology of China · University of Washington Tacoma

Communication-Efficient Distributed Training Contextual Bandits Linear Contextual Bandits Federated Learning

Ask PDF

Apr 27, 2026cs.LG

Direction-Aware Offline-to-Online Learning in Linear Contextual Bandits

Many bandit systems are deployed with offline historical data, such as past logs from earlier policies. Using these data can reduce early online exploration when they remain informative for the online problem. When the offline and online environments differ, such data can be biased for the online problem. For linear (contextual) bandits, this bias is directional: offline data may be informative in some feature directions and misleading in others. However, prior work typically controls this gap through a known Euclidean bound on the model parameters, which we prove is too coarse: even with the offline parameter known, bias in a single unknown direction can force dimension-dependent regret. To address this challenge, we introduce a directional bias certificate

(M_{\mathrm{bias}},ρ)

that measures the offline-to-online gap through an

M_{\mathrm{bias}}

-induced norm and assigns different bias budgets to different directions. Building on this certificate, we propose \emph{Ellipsoidal-MINUCB}, which augments the online learning with an offline-pooled branch that safely exploits historical data. When the certificate is known, we show that the algorithm matches the standard SupLinUCB rate in the worst case and improves when offline coverage aligns with low-bias directions. When the certificate is unknown, we estimate it adaptively from offline and accumulated online data and establish a corresponding regret guarantee. Numerical experiments support the theory and show gains in aligned regimes.

Zean Han, Ruihan Lin, Zezhen Ding +1

Department of Industrial Engineering and Decision Analytics The Hong Kong University of Science and Technology

Contextual Bandits UCB Algorithms Linear Contextual Bandits

Ask PDF

Apr 16, 2026cs.LG

Calibration-Gated LLM Pseudo-Observations for Online Contextual Bandits

Contextual bandit algorithms suffer from high regret during cold-start, when the learner has insufficient data to distinguish good arms from bad. We propose augmenting Disjoint LinUCB with LLM pseudo-observations: after each round, a large language model predicts counterfactual rewards for the unplayed arms, and these predictions are injected into the learner as weighted pseudo-observations. The injection weight is controlled by a calibration-gated decay schedule that tracks the LLM's prediction accuracy on played arms via an exponential moving average; high calibration error suppresses the LLM's influence, while accurate predictions receive higher weight during the critical early rounds. We evaluate on two contextual bandit environments - UCI Mushroom (2-arm, asymmetric rewards) and MIND-small (5-arm news recommendation) - and find that when equipped with a task-specific prompt, LLM pseudo-observations reduce cumulative regret by 19% on MIND relative to pure LinUCB. However, generic counterfactual prompt framing increases regret on both environments, demonstrating that prompt design is the dominant factor, more important than the choice of decay schedule or calibration gating parameters. We analyze the failure modes of calibration gating on domains with small prediction errors and provide a theoretical motivation for the bias-variance trade-off governing pseudo-observation weight.

Maksim Pershin, Ivan Golovanov, Pavel Baltabaev +1

Contextual Bandits Linear Contextual Bandits

Ask PDF

Oct 8, 2025cs.LG

Best-of-Both Worlds for linear contextual bandits with paid observations

We study linear contextual bandits with paid observations, where at each round the learner observes a context, selects an action, and may pay a fixed cost to observe feedback from a subset of arms. We propose two Follow-the-Regularized-Leader algorithms with Best-of-Both-Worlds guarantees. The first, Agg-SPB, extends the SPB-matching framework of Tsuchiya and Ito (2024) by aggregating context-dependent stability terms, achieving the characteristic

T^{2/3}

adversarial regret rate and logarithmic dependence on

T

in stochastic environments. The second, CE-SPB, combines arm-dependent observation probabilities with an entropy-adaptive learning rate inspired by Kuroki et al. (2024). It achieves an entropy-adaptive

\widetilde{O}(T^{2/3})

adversarial guarantee and polylogarithmic stochastic regret, while avoiding the minimum-context-mass dependence arising in the stochastic analysis of Agg-SPB. Both algorithms further extend to corrupted stochastic environments with explicit corruption-dependent guarantees. These results establish that logarithmic stochastic regret is compatible with the

T^{2/3}

adversarial regime for linear contextual bandits with paid observations, while highlighting a tradeoff between sharper horizon dependence in stochastic settings and path-dependent matching without explicit minimum-context-mass dependence.

Nathan Boyer, Dorian Baudry, Patrick Rebeschini

ENS Paris-Saclay, France · Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France · Department of Statistics, University of Oxford

Multi-Armed Bandits Follow-the-Regularized-Leader Contextual Bandits Adversarial Bandits Linear Contextual Bandits

Ask PDF

Momentum

Related topics

Latest papers 17