arXiv:2502. 08870v2 Announce Type: replace Abstract: We provide an approach for the analysis of randomised exploration algorithms like Thompson sampling that does not rely on forced optimism or posterior inflation.
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.
arXiv:2610.32910v1 Announce Type: new Abstract: Regularised reinforcement learning (RL) algorithms rely on estimators, like Monte Carlo tree search or one-step look-ahead, to provide policy, value, o...
The paper presents the first high‑probability regret bounds for both cumulative and current‑step variants of Feel‑Good Thompson Sampling (FGTS) in contextual bandits with general realizable function approximation. The bounds rely on decoupling coefficients and prior mass near the true reward function, and in the linear setting they achieve ≠d√T log(2T)+√T log(1/δ) regret with probability at least 1‑δ. This matches the dimension and horizon dependence of upper‑confidence‑bound algorithms up to logarithmic factors, while the high‑probability cost adds only linear dependence on log(1/δ).
arXiv:2607. 29375v1 Announce Type: cross Abstract: Organizations increasingly rely on sequential experimentation to improve decision-making.
The paper introduces the tilted sampling problem, where an online learner aims to sample from a Gibbs distribution defined by an unknown reward function. It defines sampling regret as the temperature‑normalized cumulative KL divergence between the learner’s distribution and the target Gibbs distribution, linking it to entropy‑regularized reward maximization. The authors develop sampling analogues of UCB and Thompson sampling, proving that sampling regret can achieve logarithmic growth in time, unlike standard regret which scales as ×O(√T).
The paper analyzes Bayesian linear bandits with isotropic Gaussian parameters, independent Gaussian arms, and Gaussian reward noise when the time horizon scales with the dimension. It derives explicit limits for the normalized posterior uncertainty and parameter overlaps, yielding exact regret curves for several policies—including Thompson sampling, posterior‑mean greedy selection, and scaled‑covariance variants. The results show that posterior‑mean greedy selection achieves the optimal Bayes regret, while Thompson sampling incurs a strictly larger leading regret whose ratio to greedy lies between one and two, approaching two for long horizons.
arXiv:2605. 09454v2 Announce Type: replace-cross Abstract: We study the $\textit{single-index bandit}$ problem, where rewards depend on an unknown one-dimensional projection of high-dimensional contexts through an unknown reward function.
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.
arXiv:2605. 20854v2 Announce Type: replace Abstract: We study a stochastic bandit algorithm motivated by retry-aware objectives that value the best outcome among multiple attempts, such as pass@$k$ and max@$k$.
arXiv:2610. 22252v1 Announce Type: new Abstract: We study how to evaluate $K$ target policies simultaneously in stochastic contextual bandits with linear reward structure.
The paper introduces CS-UCCB, an algorithm for stage‑wise constrained contextual bandits that observes only the reward and cost of the chosen action. By combining offline regression, cost confidence sets, and upper counterfactual confidence bounds, it achieves feasibility at every round and a regret of ≥O(√T) without relying on an eluder dimension, provided the reward and cost classes have polylogarithmic covering entropy and low offline estimation error. The authors also extend their results to infinite action spaces under a reward‑design condition and compare their bounds to existing eluder‑dimension‑based guarantees.