New algorithm reduces individual regret and communication costs in cooperative bandits.
problem Optimal individual and group regret in cooperative multi-agent bandits.
method Integrates a new communication policy into a learning algorithm.
result Achieves optimal individual regret and constant communication costs.
New framework for Adam-type algorithms with constant β1, improving regret analysis.
problem Theoretical vs. practical use of Adam and variants with constant β1.
method Proposed a novel framework to derive optimal, data-dependent regret bounds with constant β1.
result Optimal, data-dependent regret bounds with constant β1 are achievable without further assumptions.
New algorithm SELECT minimizes satisficing regret in bandits.
problem Minimizing regret in bandit optimization with satisficing arms.
method SELECT algorithm for satisficing regret minimization.
result SELECT achieves constant expected satisficing regret.
New algorithm reduces online logistic regression regret without exponential constant.
problem Improper learning in online logistic regression with logarithmic regret.
method Regularized empirical risk minimization with surrogate losses.
result Regret scaling as O(B log(Bn)) with low computational complexity.
EBUCB framework achieves optimal regret with bounded approximate inference error.
problem Theoretical gap between practical performance and theoretical justification of Bayesian bandit algorithms with approximate inference.
method Enhanced Bayesian Upper Confidence Bound (EBUCB) framework that accommodates bandit problems with approximate inference.
result EBUCB achieves optimal regret order O ( log T ) O(\log T) O ( log T ) under certain conditions on inference error. Mixability of a loss is known to characterise when constant regret bounds are achievable in games of prediction with expert advice through the use of Vovk's aggregating algorithm. We provide a new interpretation of mixability via convex analysis that highlights the role of the Kullback-Leibler divergence in its definit…
We prove a new minimax theorem connecting the worst-case Bayesian regret and minimax regret under partial monitoring with no assumptions on the space of signals or decisions of the adversary. We then generalise the information-theoretic tools of Russo and Van Roy (2016) for proving Bayesian regret bounds and combine th…
New algorithm reduces regret in asynchronous multiplayer bandits to constant or logarithmic levels.
problem Asynchronous multiplayer bandits in cognitive radio networks.
method Cautious Greedy algorithm with O ( T log ( T ) ) \mathcal{O}(\sqrt{T\log(T)}) O ( T log ( T ) ) minimax regret. result Cautious Greedy yields constant instance-dependent regret under certain conditions.
Paper shows re-solving heuristics have constant regret for price-based revenue management.
problem Optimal pricing policies for revenue management with time constraints.
method Proves re-solving heuristics have O ( 1 ) O(1) O ( 1 ) regret compared to optimal policies. result Improved regret bound to O ( 1 ) O(1) O ( 1 ) from O ( ln T ) O(\ln T) O ( ln T ) , complemented by Ω ( ln T ) Ω(\ln T) Ω ( ln T ) gap with fluid model. ECP optimizes expensive functions without knowing Lipschitz constant.
problem Optimizing expensive, non-convex functions with unknown Lipschitz constants.
method ECP minimizes evaluations by focusing on potentially optimal regions, eliminating Lipschitz constant estimation.
result Guaranteed no-regret performance and minimax-optimal regret bounds.
Survey of universal portfolio techniques for minimizing investment regret.
problem Minimizing investment regret in algorithmic trading.
method Explains various universal portfolio techniques and their proofs.
result Coverage of fundamental concepts and algorithms in regret minimization.
New analysis shows how temporal variability affects online learning performance.
problem Understanding the impact of temporal variability on online learning performance.
method Careful regret analysis and adaptive algorithm development.
result Proved a novel static regret bound that depends on temporal variability.
The paper honors Lai's contributions to multi-armed bandits and establishes new regret bounds.
problem Improving regret bounds in multi-armed bandit problems.
method Establishes non-asymptotic regret bounds for upper confidence bound indices.
result New regret bounds match Lai-Robbins lower bound.
Optimistic Hedge achieves optimal regret bounds in two-player zero-sum games.
problem Achieving optimal regret bounds for optimistic Hedge in two-player zero-sum games.
method Refined regret analysis and optimization problem formulation.
result Optimistic Hedge achieves O ( log m log n ) O(\sqrt{\log m \log n}) O ( log m log n ) regret bounds, matching upper and lower bounds. Algorithm finds optimal regularizers for online linear optimization.
problem Finding optimal regularizers to minimize regret in online linear optimization.
method Algorithm takes input sets and outputs an optimal regularizer for FTRL.
result Algorithm guarantees regret within a constant factor of the best possible learning algorithm.
New algorithm reduces online learning regret for bounded recall games.
problem Reducing regret in online learning with limited past information.
method Constructing a stationary bounded-recall algorithm with O ( 1 / M ) O(1/\sqrt{M}) O ( 1/ M ) regret. result Any low regret bounded-recall algorithm must be aware of past losses' order.
New method evaluates LLMs fairness in universal prediction.
problem Evaluating fairness of large language models in universal prediction.
method Introducing batch regret as a modification of average regret for LLMs.
result Asymptotical value of batch regret for add-constant predictors on memoryless and first-order Markov sources.
The paper proves a regret bound for a sub-Gaussian mixture on unbounded data.
problem Tackles the challenge of achieving regret bounds for sub-Gaussian mixtures on unbounded data.
method Uses path-wise (deterministic) regret bounds and a cumulative variance process to derive the bound.
result Shows that on a specific event, the regret is eventually bounded by ln(ln V_T).
Paper presents an algorithm for optimal regret in communicating Markov decision processes.
problem Achieving optimal regret in Markov decision processes with a communicating assumption.
method The algorithm explicitly tracks the constant K(M) to learn optimally, balancing exploration, co-exploration, and exploitation.
result The algorithm achieves asymptotically optimal regret K ( M ) log ( T ) + o ( log ( T ) ) K(M) \log(T) + \mathrm{o}(\log(T)) K ( M ) log ( T ) + o ( log ( T )) for communicating Markov decision processes. Improved cumulative regret for sequence prediction with limited expert advice.
problem Minimizing cumulative regret in sequence prediction with limited information.
method Convex combination of experts with limited observation, achieving constant regret.
result Strategies achieve constant regret independent of the horizon T, improving over standard bounds.
Optimal algorithm for minimizing regret in heavy-tailed bandits.
problem Minimizing regret in stochastic multi-armed bandits with heavy-tailed distributions.
method Proposes an optimal algorithm under the assumption of uniformly bounded moments of order (1+ε).
result Matches the lower bound exactly in the first-order term and provides a finite-time bound on its regret.
In online learning, the dynamic regret metric chooses the reference (optimal) solution that may change over time, while the typical (static) regret metric assumes the reference solution to be constant over the whole time horizon. The dynamic regret metric is particularly interesting for applications such as online reco…
Gaptron algorithm reduces mistakes in online multiclass classification.
problem Online multiclass classification with limited information.
method Randomized first-order algorithm exploiting the gap between zero-one loss and surrogate losses.
result First linear time algorithm with O ( K T ) O(K\sqrt{T}) O ( K T ) expected regret. New algorithm optimizes best arm identification with minimal regret.
problem Best arm identification in multi-armed bandit problems.
method Characterized Bayesian simple regret with continuity conditions of prior, proposed a simple algorithm.
result Proposed algorithm achieves rate-optimal Bayesian simple regret.
Consider the classical problem of predicting the next bit in a sequence of bits. A standard performance measure is {\em regret} (loss in payoff) with respect to a set of experts. For example if we measure performance with respect to two constant experts one that always predicts 0's and another that always predicts 1's …
Study on sequential prediction with log-loss, focusing on well-specified and misspecified cases.
problem Sequential prediction with log-loss under different specification conditions.
method Analysis of cumulative regret in well-specified and misspecified cases for a Gaussian location hypothesis class.
result Cumulative regrets in well-specified and misspecified cases asymptotically coincide for the d d d -dimensional Gaussian location hypothesis class. This work improves regret minimization for logistic bandits by reducing dependence on a large constant.
problem Minimizing regret in logistic bandits with reduced dependence on a large constant.
method Experimental design procedure and warmup sampling algorithm.
result Achieves a minimax regret of \(O(\sqrt{d \dotμT\log(|\mathcal{X}|)})\) in the fixed arm setting.
New algorithms reduce regret in reinforcement learning with MNL approximations.
problem Efficient reinforcement learning with MNL function approximation for MDPs.
method Proposed randomized exploration algorithms with frequentist regret guarantees.
result Achieved improved regret bounds for MNL transition models.
Study nonparametric contextual bandits with batched updates, achieving optimal regret.
problem Optimal regret in nonparametric contextual bandits with batch constraints.
method Dynamic binning of covariate space, optimal regret achieved.
result Achieves optimal regret (up to logarithmic factors) for nonparametric contextual bandits.
New algorithms reduce online learning regret by tracking gradient variation.
problem Online learning with unconstrained losses and gradient variation.
method Parameter-free algorithms with adaptive updates for L L L -smooth convex losses. result Regret bounds of order O ~ ( ∥ u ∥ V T ( u ) + L ∥ u ∥ 2 + G 4 ) \widetilde{O}(\|u\|\sqrt{V_T(u)} + L\|u\|^2+G^4) O ( ∥ u ∥ V T ( u ) + L ∥ u ∥ 2 + G 4 ) achieved without prior knowledge of comparator norm or Lipschitz constant. Improved guarantees for misspecified kernelized bandit optimization.
problem Misspecification in kernelized bandit optimization.
method Localization and domain splitting techniques.
result Logarithmic or polylogarithmic growth of misspecification amplification.
We consider K K K -armed stochastic bandits and consider cumulative regret bounds up to time T T T . We are interested in strategies achieving simultaneously a distribution-free regret bound of optimal order K T \sqrt{KT} K T and a distribution-dependent regret that is asymptotically optimal, that is, matching the κ ln T κ\ln T κ ln T lower b…
New algorithm reduces regret in collaborative multi-agent bandit problems.
problem Optimizing decisions in a network of agents with communication delays.
method Follow-the-Regularized-Leader (FTRL) algorithm with suitable regularizers and communication protocols.
result Upper bound on individual regret matches lower bound up to a constant factor.
We study the effects of approximate inference on the performance of Thompson sampling in the k k k -armed bandit problems. Thompson sampling is a successful algorithm for online decision-making but requires posterior inference, which often must be approximated in practice. We show that even small constant inference error …
New algorithm reduces regret in private online learning with optimal gap-dependent rate.
problem Optimal gap-dependent regret rate for private stochastic decision-theoretic online learning.
method Horizon-free pure-DP algorithm with exponential block partitioning and softmax selection.
result Explicit regret bound of 1000 ⋅ ( log K Δ min + log K ε ) 1000 \cdot (\frac{\log K}{Δ_{\min}}+\frac{\log K}{\varepsilon}) 1000 ⋅ ( Δ m i n l o g K + ε l o g K ) . We consider the classical stochastic multi-armed bandit but where, from time to time and roughly with frequency ε ε ε , an extra observation is gathered by the agent for free. We prove that, no matter how small ε ε ε is the agent can ensure a regret uniformly bounded in time. More precisely, we construct an algorithm with a…
Efficient algorithms for online learning with changing action sets, achieving no-approximate-regret guarantees.
problem Online learning with sleeping experts/bandits, where only a subset of actions are available each time.
method Developed computationally efficient algorithms providing no-approximate-regret guarantees for the general problem and better approximation ratios for special cases.
result Achieved no-approximate-regret guarantees for the general sleeping expert/bandit problems and better approximation ratios for specific cases.
MINTS uses a minimalist Bayesian framework to tackle multi-armed bandits with structural constraints.
problem Sequential decision-making under uncertainty with complex structural constraints.
method Minimalist Bayesian framework with profile likelihood to eliminate nuisance parameters.
result MINTS achieves near-optimal regret guarantees and adapts to unimodal structure.
New algorithm reduces regret with diverse contexts in bandits.
problem Impact of context diversity on stochastic linear contextual bandits.
method Design of LinUCB-d algorithm and analysis of its regret performance.
result Cumulative expected regret is bounded by a constant under diverse context assumption.
Study shows nonstationary bandits require T-dependent regret even with minimal nonstationarity.
problem Understanding satisficing regret in nonstationary multi-armed bandits.
method Developed a novel Fano-based framework for nonstationary bandits with a post-interaction reference construction.
result Optimal regret scales with T even with minimal nonstationarity, contrasting with stationary case.
A new reinforcement learning framework separates users into risk-tolerant and risk-averse groups for better performance.
problem Improving performance for risk-averse users in reinforcement learning.
method Introducing a tiered reinforcement learning approach with two policies: π e x t O π^{ ext{O}} π e x t O and π e x t E π^{ ext{E}} π e x t E . result Achieving constant regret for risk-averse users, independent of the number of episodes.
Optimal algorithm found for collaborative learning in bandits with optimal regret bounds.
problem Minimizing regret in collaborative multi-agent bandit problems.
method Proposed an algorithm with optimal regret bounds for collaborative multi-agent multi-armed bandit model.
result First algorithm with order optimal regret bounds for collaborative bandit model.
We study online optimization of smoothed piecewise constant functions over the domain [0, 1). This is motivated by the problem of adaptively picking parameters of learning algorithms as in the recently introduced framework by Gupta and Roughgarden (2016). Majority of the machine learning literature has focused on Lipsc…
A new algorithm optimizes time-varying functions with non-constant evaluation times.
problem Optimizing functions that change over time with varying evaluation times.
method Proposes a novel time-varying Bayesian optimization algorithm.
result Establishes a regret bound for the proposed algorithm.
Nowadays, online learning is an appealing learning paradigm, which is of great interest in practice due to the recent emergence of large scale applications such as online advertising placement and online web ranking. Standard online learning assumes a finite number of samples while in practice data is streamed infinite…
Improved Thompson Sampling using fractional posteriors achieves better regret bounds.
problem Optimizing regret in stochastic multi-armed bandit problems.
method Using α \alpha α -posterior distributions, derived frequentist regret bounds. result Instance-dependent and instance-independent regret bounds established.
Thompson sampling for multi-armed bandit problems is known to enjoy favorable performance in both theory and practice. However, it suffers from a significant limitation computationally, arising from the need for samples from posterior distributions at every iteration. We propose two Markov Chain Monte Carlo (MCMC) meth…
New algorithm learns and unlearns from streaming data efficiently.
problem Continuous learning and unlearning from production data streams.
method Translated batch unlearning techniques to online setting using regret, sample complexity, and deletion capacity.
result Achieved logarithmic regret bound of O ( ln T ) \mathcal{O}(\ln{T}) O ( ln T ) for online unlearning.