Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit

2024-11-19 · Seok-Jin Kim, Min-hwan Oh

We study the performance guarantees of exploration-free greedy algorithms for the linear contextual bandit problem. We introduce a novel condition, named the \textit{Local Anti-Concentration} (LAC) condition, which enables a greedy bandit algorithm to achieve provable efficiency. We show that the LAC condition is satisfied by a broad class of distributions, including Gaussian, exponential, uniform, Cauchy, and Student's~$t$ distributions, along with other exponential family distributions and their truncated variants. This significantly expands the class of distributions under which greedy algorithms can perform efficiently. Under our proposed LAC condition, we prove that the cumulative expected regret of the greedy algorithm for the linear contextual bandit is bounded by $O(\operatorname{poly} \log T)$. Our results establish the widest range of distributions known to date that allow a sublinear regret bound for greedy algorithms, further achieving a sharp poly-logarithmic regret.

📄 PDF Abstract BibTeX arXiv:2411.12878

Code (0)

등록된 구현이 없습니다.

Why Most Optimism Bandit Algorithms Have the Same Regret Analysis: A Simple Unifying Theorem

2025-12-20 · Vikram Krishnamurthy arxiv

Several optimism-based stochastic bandit algorithms -- including UCB, UCB-V, linear UCB, and finite-arm GP-UCB -- achieve logarithmic regret using proofs that, despite superficial differences, follow essentially the same…

Conformal-Style Quantile Analyses for Stochastic Bandits

2026-05-08 · Chengyu Du, Mengfan Xu arxiv

Stochastic bandit algorithms are usually analyzed under a mean-reward criterion, yet many problems favor arms with strong upper-tail performance, which we study herein. For a fixed miscoverage level $α$, the natural up…

Federated Q-Learning: Linear Regret Speedup with Low Communication Cost

2023-12-22 · Zhong Zheng, Fengyu Gao, Lingzhou Xue, Jing Yang

In this paper, we consider federated reinforcement learning for tabular episodic Markov Decision Processes (MDP) where, under the coordination of a central server, multiple agents collaboratively explore the environment …

Q-Learning reinforcement-learning Reinforcement Learning

When Classic Cache Policies Fail: Learning-Augmented Replacement for Semantic Retrieval Buffers

2026-07-01 · Yushi Sun, Bowen Cao, Wai Lam hf

LLM agents increasingly rely on retrieval buffers to store and reuse past experience, yet the cache management policies governing these buffers remain largely ad-hoc. We formalize this as an online semantic cache replace…

Semantic Retrieval

Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions

2022-05-25 · Adam Block, Max Simchowitz

Due to the drastic gap in complexity between sequential and batch statistical learning, recent work has studied a smoothed sequential learning setting, where Nature is constrained to select contexts with density bounded …