New algorithm reduces regret from sqrt(T) to polylog(T) in stochastic contextual linear bandits.
problem Achieving logarithmic regret in stochastic contextual linear bandits.
method Low Regret Stochastic Contextual Bandits ( exttt{LR-SCB}) algorithm, exploiting stochastic contexts and parameter estimation.
result Logarithmic regret (polylog(T)) achieved, improving over sqrt(T) lower bound.
The paper analyzes the sliding regret of stochastic bandit algorithms.
problem Measuring the one-shot behavior of no-regret algorithms in stochastic bandits.
method Introducing sliding regret to measure the worst pseudo-regret over a time-window.
result Randomized methods have optimal sliding regret, while index policies have the worst possible sliding regret.
Study on Pareto optimality in multi-objective bandit problems.
problem Pareto optimality in multi-objective multi-armed bandit problems.
method Formulated adversarial multi-objective multi-armed bandit, defined Pareto regrets, presented algorithms, established upper and lower bounds.
result New algorithms are optimal in adversarial settings and nearly optimal in stochastic settings.
New algorithm minimizes worst-case regret in uncertain, time-varying dynamics.
problem Model-based policy learning in uncertain, time-varying dynamics.
method Planning regret metric and iterative algorithm for minimizing it.
result Empirical evidence shows the proposed algorithm outperforms existing methods.
Algorithm reduces regret in SSP problems with LFA.
problem Finding shortest paths in stochastic environments with linear approximations.
method Uses linear function approximation and stationary policies to minimize regret.
result Achieves sublinear regret under minimal assumptions.
Study on individual regret in cooperative MAB with agents communicating over a graph.
problem Individual regret in cooperative stochastic multi-armed bandits with communication constraints.
method Analyzed COOP-SE algorithm, derived individual regret bounds under various communication constraints.
result First to show an individual regret bound in cooperative stochastic MAB independent of graph diameter.
Unified algorithm for optimizing rewards in stochastic path problems.
problem Optimizing rewards in stochastic path problems with unknown reward scales.
method A simple optimistic algorithm with regret guarantees.
result Regret bound matches best known results for SSP with all non-positive rewards.
New algorithm reduces dynamic regret without prior function change knowledge.
problem Non-stationary stochastic optimization with bandit feedback.
method Fixed step sizes combined with multi-scale sampling framework.
result Achieves optimal dynamic regret without prior function change knowledge.
New algorithm achieves optimal regret in non-stochastic control, showing stochasticity is not beneficial.
problem Achieving optimal control in non-stochastic systems with adversarial noise.
method Novel online Newton step algorithm adapted to adversarial disturbances, using policy regret bounds.
result Optimal O ~ ( T ) \widetilde{\mathcal{O}}(\sqrt{T}) O ( T ) regret achieved in unknown dynamics, p o l y ( log T ) \mathrm{poly}(\log T) poly ( log T ) regret in known dynamics. New Thompson sampling algorithm for stochastic partial monitoring achieves logarithmic regret.
problem Limited feedback in sequential learning problems.
method Developed a novel Thompson-sampling-based algorithm to sample from the posterior distribution exactly.
result Achieved logarithmic regret bound of O(log T) for a linearized variant of the problem.
Study on policy gradient for stochastic bandits using diffusion approximation.
problem Improving policy gradient methods for stochastic bandits with optimal regret bounds.
method Continuous-time diffusion approximation of policy gradient with learning rate analysis.
result Proved optimal regret bound of O ( k log ( k ) log ( n ) / η ) O(k \log(k) \log(n) / η) O ( k log ( k ) log ( n ) / η ) for η = O ( Δ 2 / log ( n ) ) η= O(Δ^2/\log(n)) η = O ( Δ 2 / log ( n )) . 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).
Improved regret bounds for online convex optimization under stochastic and adversarial settings.
problem Interpolating between stochastic and adversarial online convex optimization.
method Optimistic online mirror descent (OMD) for the Stochastically Extended Adversarial (SEA) model.
result Established new regret bounds for various function classes.
A new batch ensemble method reduces regret in stochastic bandits.
problem Efficiently balancing exploration and exploitation in online RL.
method Proposes a batch ensemble scheme to achieve near-optimal regret.
result Proves near-optimal regret with a single parameter independent of variance.
New method tackles endogeneity in online learning with improved regret bounds.
problem Endogeneity in real data due to omitted variables, strategic behaviors, etc.
method O2SLS (Online Two-Stage Least Squares) for Instrumental Variable (IV) regression.
result O2SLS achieves identification and oracle regret bounds for stochastic online learning.
Unified framework for analyzing online convex optimization across various settings.
problem Analyzing online convex optimization in different settings and feedback types.
method Unified framework allowing systematic proposal and analysis of meta-algorithms.
result Comparable regret bounds for various feedback types and adversary types.
New insights into balancing reward and fairness in stochastic MAB.
problem Balancing reward and fairness in stochastic multi-armed bandits.
method Formulated a penalization framework and proposed a hard-threshold UCB-like algorithm.
result Asymptotic fairness, nearly optimal regret, better reward-fairness tradeoff.
New algorithms reduce regret in online MDPs by adapting to data and variance.
problem Adapting to both adversarial and stochastic environments in online MDPs.
method Develops algorithms based on global optimization and policy optimization, using optimistic follow-the-regularized-leader with log-barrier regularization.
result Achieves refined data-dependent and variance-dependent regret bounds.
We derive an algorithm that achieves the optimal (within constants) pseudo-regret in both adversarial and stochastic multi-armed bandits without prior knowledge of the regime and time horizon. The algorithm is based on online mirror descent (OMD) with Tsallis entropy regularization with power α = 1 / 2 α=1/2 α = 1/2 and reduced-varian…
New bounds for online convex optimization between stochastic and adversarial settings.
problem Understanding optimization tasks that are neither i.i.d. nor fully adversarial.
method Establishing novel regret bounds exploiting smoothness of expected losses.
result Regret bounds match expected rates in the fully i.i.d. case and gracefully deteriorate in the fully adversarial case.
Balances and eliminates base algorithms in bandits and RL to bound total regret.
problem Model selection in bandits and reinforcement learning with unknown optimal regret.
method Balances and eliminates base algorithms based on candidate regret bounds.
result Total regret bound is the best valid candidate regret bound times a small multiplicative factor.
A meta-UCB method combines stochastic bandit algorithms.
problem Combining multiple stochastic bandit algorithms efficiently.
method Meta-UCB procedure solving an N-armed bandit problem.
result Final regret depends only on the best base algorithm's regret.
Combines multiple bandit algorithms to create a nearly optimal single algorithm.
problem Designing a single bandit algorithm that performs nearly as well as the best individual algorithm in a stochastic environment.
method Develops two general corralling algorithms that achieve favorable regret guarantees.
result The regret of the corralling algorithms is no worse than the best individual algorithm's performance.
Study shows certainty equivalent policy minimizes regret in continuous-time systems.
problem Minimizing regret in continuous-time stochastic linear-quadratic systems.
method Theoretical analysis of randomized certainty equivalent policy.
result Establishes square-root of time regret bounds and linear scaling with parameters.
New algorithms minimize regret in both adversarial and stochastic contexts.
problem Minimizing regret in linear contextual bandits.
method Best-of-both-worlds algorithms using FTRL with Shannon entropy regularizer.
result Achieves near-optimal regret bounds in both adversarial and stochastic regimes.
We study the stochastic multi-armed bandit problem when one knows the value μ ( ⋆ ) μ^{(\star)} μ ( ⋆ ) of an optimal arm, as a well as a positive lower bound on the smallest positive gap Δ Δ Δ . We propose a new randomized policy that attains a regret {\em uniformly bounded over time} in this setting. We also prove several lower bound…
Improved algorithm for bandits with delayed feedback, combining adversarial and stochastic performance.
problem Adversarial and stochastic multiarmed bandits with delayed feedback.
method Modified Zimmert and Seldin's algorithm with near-optimal regret guarantees.
result Near-optimal regret guarantees in both adversarial and stochastic settings.
Improved online convex optimization bounds between stochastic and adversarial settings.
problem Understanding optimization tasks that are neither i.i.d. nor fully adversarial.
method Establishing novel regret bounds exploiting smoothness of expected losses.
result Regret bounds improve on previous results by reducing dependence on maximum gradient length to variance of gradients.
Data-driven model selection reduces regret in sequential decisions.
problem Optimizing model selection in stochastic environments with bandit feedback.
method Data-driven regret balancing for model selection.
result Meta-learner selects the best base learner based on actual realized regret.
Bayesian bandit algorithms with approximate inference improve regret bounds in stochastic linear bandits.
problem Theoretical justification for Bayesian bandit algorithms with approximate inference in stochastic linear bandits.
method Proposed a theoretical framework to analyze approximate inference impact and conducted frequentist regret analysis on LinTS and LinBUCB.
result LinTS and LinBUCB preserve their original regret upper bounds with larger constant terms in approximate inference settings.
This paper addresses missing covariates in stochastic linear bandits, providing a high-probability regret bound.
problem Effect of missing covariates on regret in stochastic linear bandit algorithms.
method Proposes an algorithm that provides a high-probability upper bound on regret in terms of covariate sampling probabilities.
result Regret degrades due to missingness by at most ζ m i n 2 ζ_{min}^2 ζ min 2 , where ζ m i n ζ_{min} ζ min is the minimum probability of observing covariates. New algorithms for batched dueling bandits with improved regret bounds.
problem Batched dueling bandits with noisy pairwise comparisons.
method Developed algorithms for two settings: Condorcet winner and strong stochastic transitivity.
result Regret bounds match sequential bounds using only a logarithmic number of batches.
Improved algorithms for stochastic linear bandits using tighter confidence sequences.
problem Stochastic linear bandits with improved worst-case regret guarantees.
method Novel tail bound for adaptive martingale mixtures to construct tighter confidence sequences.
result Linear bandit algorithm achieves competitive worst-case regret.
Improved prediction algorithm for 'easy' sequences with reduced regret.
problem Prediction with expert advice for 'easy' sequences.
method Variant of NormalHedge algorithm using second-order ε ε ε -quantile regret bound. result Second-order ε ε ε -quantile regret bound of O ( V T log ( V T / ε ) ) O\big(\sqrt{V_T \log(V_T/ε)}\big) O ( V T log ( V T / ε ) ) for V T > log N V_T > \log N V T > log N . We present a new anytime algorithm that achieves near-optimal regret for any instance of finite stochastic partial monitoring. In particular, the new algorithm achieves the minimax regret, within logarithmic factors, for both "easy" and "hard" problems. For easy problems, it additionally achieves logarithmic individual…
Two-stage mechanism designs reduce regret in recommender systems with stochastic covariates.
problem Designing effective recommender systems with user covariates sampled online.
method Two-stage algorithm integrating incentivized exploration with offline learning methods.
result Achieves sublinear regret while maintaining incentive compatibility.
Develops model selection for bandits balancing adversarial and stochastic guarantees.
problem Model selection in bandit scenarios with simultaneous adversarial and stochastic high-probability regret.
method Nested policy classes, balanced candidate regret bounds, mis-specification tests.
result Best of both world guarantees in linear bandits with simultaneous adversarial and stochastic environments.
Algorithm minimizes regret in dueling bandits with contextualized utilities.
problem Minimizing regret in dueling bandits with context-dependent utilities.
method Proposes CoLSTIM algorithm based on perturbed utility estimates.
result Achieves regret of order i l d e O ( d T ) ilde O(\sqrt{dT}) i l d e O ( d T ) . Paper develops robust estimators and strategies for stochastic MABs with heavy-tailed rewards.
problem Stochastic multi-armed bandits with heavy-tailed rewards.
method Proposes a novel robust estimator and perturbation-based exploration strategy.
result Develops upper and lower regret bounds for various perturbations.
Optimizes regret distribution in stochastic bandits for risk balance.
problem Balancing regret expectation and tail risk in stochastic bandits.
method Characterizes optimal regret tail probability for any threshold, proposes new policies.
result Discovers an intrinsic gap in optimal tail rate based on time horizon uncertainty.
New algorithm reduces regret in stochastic bandit convex optimization.
problem Optimizing decisions in uncertain environments with convex losses.
method Introduces a second-order method for zeroth-order stochastic convex bandits.
result Regret bound of ( 1 + r / d ) [ d 1.5 n + d 3 ] p o l y l o g ( n , d , r ) (1 + r/d)[d^{1.5} \sqrt{n} + d^3] polylog(n, d, r) ( 1 + r / d ) [ d 1.5 n + d 3 ] p o l y l o g ( n , d , r ) . Improved online Q-learning for MDPs with concentration bounds.
problem Online Q-learning in infinite-horizon discounted MDPs with sublinear regret for large gaps.
method Smoothed ε n ε_n ε n -Greedy exploration scheme combining ε n ε_n ε n -greedy and Boltzmann exploration, analyzed using concentration bounds for contractive Markovian stochastic approximation. result Near- i l d e O ( N 9 / 10 ) ilde{O}(N^{9/10}) i l d e O ( N 9/10 ) regret bound for Smoothed ε n ε_n ε n -Greedy exploration scheme. Study finds optimal regret bound for multi-armed bandit problem with expert advice.
problem Optimizing decision-making in a multi-armed bandit problem with expert advice.
method Proved a tight lower bound matching the upper bound of Kale (2014) for minimax expected regret.
result The minimax optimal expected regret is Θ(√(T K log (N/K))) for the problem.
Paper tackles online learning with interval regret, achieving adaptive bounds.
problem Non-stationary online learning over time intervals.
method Two-layer online ensemble structure with gradient variation.
result Achieves strong theoretical guarantees with adaptive bounds.
New algorithm optimizes multi-armed bandit performance in stochastic and adversarial settings.
problem Optimizing multi-armed bandit performance in both stochastic and adversarial environments.
method Follow-the-regularized-leader method with adaptive learning rates.
result First BOBW algorithm with gap-variance-dependent regret bounds in adversarial settings.
Algorithm learns both stochastic and adversarial MDPs with best-of-both-worlds guarantees.
problem Learning episodic MDPs with known transition and bandit feedback.
method Follow-the-Regularized-Leader method with a hybrid regularizer.
result Achieves O ( l o g T ) \mathcal{O}(log T) O ( l o g T ) regret for stochastic losses and i l d e O ( T ) ilde{\mathcal{O}}(\sqrt{T}) i l d e O ( T ) regret for adversarial losses. The paper addresses frequentist regret of Linear Thompson Sampling in stochastic linear bandits.
problem The frequentist regret of Linear Thompson Sampling (LinTS) is worse than its Bayesian counterpart.
method The paper proves the fundamental nature of the frequentist regret bound for LinTS and proposes a data-driven version of LinTS to achieve minimax optimal frequentist regret.
result The frequentist regret bound for LinTS is O ~ ( d d T ) \widetilde{\mathcal{O}}(d\sqrt{dT}) O ( d d T ) , which is the best possible under certain conditions. New strategy achieves optimal regret without communication or collisions in multi-player bandit.
problem Cooperative multi-player stochastic multi-armed bandit with shared randomness.
method Combination of combinatorial approach to generalize geometric intuition.
result Achieves near-optimal regret i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) for any number of players and arms without collisions.