arXiv:2606. 28616v1 Announce Type: new Abstract: In stochastic linear bandits, the canonical Upper Confidence Bound (UCB) algorithm admits a simple frequentist regret analysis but can be computationally demanding, while Thompson Sampling (TS) is computationally attractive yet typically harder to analyze due to its non-optimistic nature.
By Toshinori Kitamura, Shuai Liu, Csaba Szepesv\'ari
arXiv:2502. 13467v2 Announce Type: replace Abstract: The $K$-Max combinatorial multi-armed bandit problem arises in applications such as recommendation and distributed decision making, where the reward is determined by the maximum outcome among $K$ selected arms.
By Yu Chen, Siwei Wang, Longbo Huang, Wei Chen
arXiv:2607. 02891v1 Announce Type: new Abstract: 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.
By Zihao Hu, Yuan Yao, Jiheng Zhang, Zhengyuan Zhou
arXiv:2607. 23679v1 Announce Type: new Abstract: Recent years have witnessed increasing interests in tackling heteroscedastic noise in bandits and reinforcement learning.
By Heyang Zhao, Tianyuan Jin, Weixin Wang, Vincent Y. F. Tan, Pan Xu, Quanquan Gu
The paper investigates preference-based bandits where a learner selects pairs of arms and receives binary preference feedback modeled by Bradley–Terry. It introduces the locally sensitive eluder dimension, a new complexity measure for logistic preference feedback, and proposes the GINOP algorithm that uses log-loss confidence sets to balance optimism and exploration. The authors prove a first-order regret bound showing that learning with preference feedback can be as statistically efficient as learning from direct rewards, and they validate their theory with empirical experiments.
By Ahmed Ben Yahmed (CREST, ENSAE Paris, FAIRPLAY), Marc Abeille (FAIRPLAY), Cl\'ement Calauz\`enes (FAIRPLAY)
The paper investigates stochastic contextual bandits in an agnostic setting, aiming to compete with the best policy in a given class without assuming realizability or specific loss/reward models. It introduces an algorithm that updates the policy each round by minimizing a pessimistic objective— a clipped inverse‑propensity estimate of the policy value plus a variance penalty— and proves the first fast regret rates relative to the best‑in‑class policy. By exploiting entropy assumptions on the policy class and a H"olderian error‑bound condition, the authors achieve fast best‑in‑class regret rates, including polylogarithmic rates in the parametric case, using a sequential self‑normalized maximal inequality for bounded martingale empirical processes to derive uniform variance‑adaptive confidence bounds and ensure pessimism under adaptive data collection.
By Samuel Girard, Aurelien Bibaut, Arthur Gretton, Nathan Kallus, Houssam Zenati