Mutation improves FTRL convergence in zero-sum games.
problem Lack of last-iterate convergence in FTRL variants.
method Introduced mutation to perturb action probabilities in FTRL.
result M-FTRL converges to Nash equilibria under full-information feedback.
New algorithm expands FTRL framework with improved worst-case regret bounds.
problem Online learning with improved worst-case regret bounds.
method Generalized implicit Follow-The-Regularized-Leader (FTRL) algorithm.
result Unified framework for designing updates improving worst-case regret bounds.
Improved FTRL algorithm for multi-armed bandits with various regularizers and multiple optimal arms.
problem Designing adaptive multi-armed bandit algorithms that perform optimally in both stochastic and adversarial settings.
method Follow-the-Regularized-Leader (FTRL) algorithm with a broad family of regularizers and a new learning rate schedule.
result Uniqueness of optimal arm assumption is unnecessary for FTRL with a broad family of regularizers.
FTRL algorithm with negative entropy regularizer achieves best-of-three-world results for linear bandits.
problem Designing an FTRL algorithm for linear bandits with optimal regret bounds.
method Follow-the-regularized-leader (FTRL) algorithm with negative entropy regularizer.
result Regret bounds achieve the same or nearly the same order as detect-switch type algorithm but with simpler design.
New algorithm optimizes multi-armed bandits with low computational cost.
problem Optimizing multi-armed bandits with low computational cost.
method Proposes a new FTPL algorithm with optimistic principle for ambiguity.
result Unified regret analysis and low computational costs.
New study shows FTRL mechanism works with correlated events.
problem Forecasting competitions with correlated events.
method Introduces block correlation and uses FTRL mechanism.
result FTRL mechanism retains ε ε ε -optimal guarantee with O ( b 2 log ( n ) / ε 2 ) O(b^2 \log(n)/ε^2) O ( b 2 log ( n ) / ε 2 ) events for correlated events. Paper generalizes VB-FTRL for online learning of quantum states with logarithmic loss.
problem Online learning of quantum states with logarithmic loss.
method Generalizes VB-FTRL algorithm for LL-OLQS with polynomial-time implementation.
result Achieves a regret rate of O ( d 2 log ( d + T ) ) O (d^2 \log (d + T)) O ( d 2 log ( d + T )) for LL-OLQS. New adaptive learning rate for FTRL reduces regret to Θ(T^2/3).
problem Minimax regret of Θ(T^2/3) in online learning.
method Adaptive learning rate framework matching stability, penalty, and bias terms.
result Improves Best-of-Both-Worlds (BOBW) regret upper bounds.
New algorithm optimizes AUC for sparse high-dimensional data in online learning.
problem Optimizing AUC for imbalanced classification with high-dimensional sparse data.
method Proposes extsc{FTRL-AUC} algorithm with reduced per-iteration cost and sparsity.
result Significantly improves AUC scores and model sparsity in real-world datasets.
Study learns optimal strategies in imperfect information games with self-play.
problem Learning optimal strategies in imperfect information games.
method Proposes Follow the Regularized Leader (FTRL) algorithms for imperfect information games.
result Proposes two FTRL algorithms: Balanced FTRL and Adaptive FTRL.
New adaptive learning rate improves FTRL's adaptivity to sparsity, game-dependency, and best-of-both-worlds.
problem Improving adaptivity in sequential decision-making problems.
method Developed a stability-penalty-adaptive (SPA) learning rate for FTRL.
result First BOBW algorithm with sparsity-dependent bound.
New bounds for online portfolio selection without smoothness assumptions.
problem Online portfolio selection with non-Lipschitz, non-smooth losses.
method Data-dependent bounds using novel smoothness characterizations and FTRL with self-concordant regularizers.
result Achieves logarithmic regrets when data is 'easy' and sublinear worst-case regrets.
Improved algorithm reduces regret in corrupted expert advice setting.
problem Prediction with expert advice in the presence of adversarial corruption.
method Multiplicative Weights algorithm with decreasing step sizes.
result Achieves constant regret and optimal performance in various environments.
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.
Adaptive learning rate improves FTRL's performance in online learning.
problem Optimizing FTRL's learning rate for competitive regret in online learning.
method Formulated as a sequential decision-making problem, introduced competitive analysis framework, and proposed stability-penalty matching update rules.
result Achieved a constant competitive ratio under specific conditions, enabling Best-Of-Both-Worlds algorithms.
Unified high-probability regret bounds for online convex optimisation with randomised gradient estimators.
problem Online convex optimisation with randomised gradient estimators for ℓ q \ell_q ℓ q -Lipschitz losses. method FTRL with randomised two-point finite-difference gradient estimators based on cone-measure sampling from ℓ r \ell_r ℓ r -spheres. result Unified high-probability regret bounds for all p , q , r ∈ [ 1 , ∞ ] p,q,r \in [1,\infty] p , q , r ∈ [ 1 , ∞ ] . Adaptive online learning algorithm improves history forgetting in nonstationary environments.
problem Adversarial nonstationary environments where future data can be very different from past data.
method Discounted regret in online convex optimization, FTRL-based algorithm, adaptive learning rate.
result Improves classical gradient descent with constant learning rate in online convex optimization.
Study on online regression with noise, achieving near-optimal regret bounds.
problem Online generalized linear regression with stochastic noise.
method Sharp analysis of FTRL algorithm for stochastic label noise.
result Achieved near-optimal regret bounds for O ( σ 2 d log T ) + o ( log T ) O(σ^2 d \log T) + o(\log T) O ( σ 2 d log T ) + o ( log T ) . New algorithm reduces regret in both adversarial and stochastic contexts.
problem Contextual combinatorial semi-bandits with adversarial and corrupted stochastic regimes.
method Follow-the-Regularized-Leader (FTRL) framework with Shannon entropy regularizer, accelerated by Karush-Kuhn-Tucker conditions.
result Achieves O ~ ( T ) \widetilde{\mathcal{O}}(\sqrt{T}) O ( T ) regret in adversarial and O ~ ( ln T ) \widetilde{\mathcal{O}}(\ln T) O ( ln T ) regret in corrupted stochastic regimes. Adapting Hedge algorithm for semi-adversarial data with root-entropy regularization.
problem Minimizing regret in prediction with expert advice under varying distributions.
method Follow-the-Regularized-Leader (FTRL) with root-entropy regularization.
result Adaptive minimax optimal regret across all levels of constraint sets.
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.
Paper optimizes FTPL for adversarial and stochastic bandits with specific tail distributions.
problem Optimizing Follow-the-Perturbed-Leader (FTPL) policy for bandit problems.
method Analyzes FTPL with Fréchet-type tail distributions in adversarial and stochastic settings.
result FTPL with certain Fréchet-type tail distributions achieves O ( K T ) \mathcal{O}(\sqrt{KT}) O ( K T ) regrets in adversarial bandits. Unified algorithm for linear bandits with improved regret bound.
problem Adversarial linear bandits with improved regret.
method Self-concordant perturbations in FTPL framework.
result Regret bound of O ( d n ln n ) \mathcal{O}(d\sqrt{n \ln n}) O ( d n ln n ) for hypercube and ℓ 2 \ell_2 ℓ 2 ball. New algorithm achieves best-of-both-worlds performance in various online learning settings.
problem Achieving optimal performance in both adversarial and stochastic online learning settings.
method General reduction from best-of-both worlds to FTRL and OMD algorithms.
result Transformed existing algorithms into new ones with best-of-both-worlds guarantees.
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.
Efficient algorithm converges to Nash equilibrium in bilinear problems with bandit feedback.
problem Learning dynamics in bilinear saddle-point problems with bandit feedback.
method Uncoupled learning algorithm combining experimental design and FTRL with a tailored regularizer.
result Last-iterate convergence rate of i l d e O ( T − 1 / 4 ) ilde{O}(T^{-1/4}) i l d e O ( T − 1/4 ) in high probability. Optimizes quantile and semi-adversarial regret with novel root-logarithmic regularizers.
problem Minimizes regret in adversarial and semi-adversarial online learning.
method FTRL with root-logarithmic regularizers for quantile and semi-adversarial settings.
result Achieves minimax optimal regret bounds in both paradigms.
We propose a new algorithm for adversarial multi-armed bandits with unrestricted delays. The algorithm is based on a novel hybrid regularizer applied in the Follow the Regularized Leader (FTRL) framework. It achieves O ( k n + D log ( k ) ) \mathcal{O}(\sqrt{kn}+\sqrt{D\log(k)}) O ( k n + D log ( k ) ) regret guarantee, where k k k is the number of arms, n n n is the …
New algorithms minimize regret with global costs in online learning.
problem Minimizing regret in online learning with global costs.
method Extended FTRL algorithms for Blackwell's approachability.
result First bounds on regret minimization with explicit dependence in p p p and d d d . Near-optimal per-action regret bounds for sleeping bandits are derived.
problem Optimizing performance in sleeping bandits where arms and losses are chosen by an adversary.
method Directly minimizing per-action regret using generalized versions of EXP3, EXP3-IX, and FTRL with Tsallis entropy.
result Near-optimal bounds of order O ( T A ln K ) O(\sqrt{TA\ln{K}}) O ( T A ln K ) and O ( T A K ) O(\sqrt{T\sqrt{AK}}) O ( T A K ) are obtained. Paper optimizes multi-agent learning in Markov games with generative model.
problem Learning Nash or CCE equilibria in multi-agent Markov games.
method Develops \myalg~algorithm and adaptive sampling scheme using FTRL method.
result Minimax-optimal learning of CCE with minimal samples.
Advances FTPL results for bandit problems with unbounded perturbations.
problem Improving analytical foundations of FTPL in bandit problems.
method Revisiting classical FTRL-FTPL duality for unbounded perturbations.
result Establishes Best-of-Both-Worlds (BOBW) results for FTPL under a broad family of asymmetric unbounded perturbations.
New algorithm bounds MAB regret for unknown scale and magnitude of losses.
problem Adversarial Multi Armed Bandits with unknown scale and magnitude of losses.
method Design a bandit Follow The Regularized Leader (FTRL) algorithm with adaptive learning rate.
result First MAB bounds that adapt to L 2 L_2 L 2 and L 1 L_1 L 1 norms of losses. Develops a strategy to minimize loss in both stochastic and adversarial environments for linear contextual bandits.
problem Linear contextual bandits with adversarial corruption.
method Proposes a novel strategy called Best-of-Both-Worlds (BoBW) RealFTRL, extending RealLinExp3 and FTRL.
result Regret upper bound of $O\left(\min\left\{\frac{(\log(T))^3}{Δ_{*}} + \sqrt{\frac{C(\log(T))^3}{Δ_{*}}},\ \ \sqrt{T}(\log(T))^2
ight\}
ight)$ , showing effectiveness in both stochastic and adversarial environments.
New aggregation strategy handles unbounded losses with regret bounds.
problem Online optimization with unbounded loss functions.
method Follow The Regularized Leader (FTRL) with φ-divergence.
result Worst regret bound for unbounded losses with alternative divergences.
New algorithm reduces regret and constraint violation in online convex optimization with predictions.
problem Online convex optimization with time-varying constraints and predictions.
method Primal-dual algorithm combining Follow-The-Regularized-Leader with adaptive steps.
result Achieves O ( T 3 − β 4 ) \mathcal O(T^{\frac{3-β}{4}}) O ( T 4 3 − β ) regret and O ( T 1 + β 2 ) \mathcal O(T^{\frac{1+β}{2}}) O ( T 2 1 + β ) constraint violation bounds. Develops a Best-of-Both-Worlds algorithm for linear contextual bandits with Tsallis entropy.
problem Linear contextual bandits with i.i.d. contexts.
method Follow-The-Regularized-Leader (FTRL) with Tsallis entropy.
result Achieves $O\left(\log(T)^{\frac{1+β}{2+β}}T^{\frac{1}{2+β}}
ight)$ regret under margin condition.
Recently, much work has been done on extending the scope of online learning and incremental stochastic optimization algorithms. In this paper we contribute to this effort in two ways: First, based on a new regret decomposition and a generalization of Bregman divergences, we provide a self-contained, modular analysis of…
This paper considers online convex optimization (OCO) problems - the paramount framework for online learning algorithm design. The loss function of learning task in OCO setting is based on streaming data so that OCO is a powerful tool to model large scale applications such as online recommender systems. Meanwhile, real…
Paper proves suboptimal convergence rate of last iterate for SGDM.
problem Proves suboptimal convergence rate of last iterate for SGDM.
method Focuses on convergence rate of last iterate of SGDM, introduces Follow-The-Regularized-Leader-based algorithms.
result Shows optimal convergence rate of last iterate for unconstrained convex stochastic optimization problems.
FTPL with Fréchet perturbation achieves near optimal regret bounds for m-set semi-bandit problems.
problem Optimizing regret bounds for m-set semi-bandit problems in adversarial and stochastic settings.
method Follow-the-Perturbed-Leader (FTPL) with Fréchet perturbation.
result Achieves near optimal regret bounds of O ( n m ( d log ( d ) + m 5 / 6 ) ) \mathcal{O}(\sqrt{nm}(\sqrt{d\log(d)}+m^{5/6})) O ( nm ( d log ( d ) + m 5/6 )) in adversarial setting and logarithmic regret in stochastic setting. This paper considers the stability of online learning algorithms and its implications for learnability (bounded regret). We introduce a novel quantity called {\em forward regret} that intuitively measures how good an online learning algorithm is if it is allowed a one-step look-ahead into the future. We show that given…
Study online learning in MDPs with aggregate bandit feedback, achieving low regret in both stochastic and adversarial settings.
problem Online learning in finite-horizon episodic MDPs with aggregate bandit feedback.
method Best-of-both-worlds (BOBW) algorithms using FTRL over occupancy measures, self-bounding techniques, and new loss estimators.
result First BOBW algorithms for episodic tabular MDPs with aggregate bandit feedback achieving O ( log T ) O(\log T) O ( log T ) regret in stochastic and O ( T ) {O}(\sqrt{T}) O ( T ) regret in adversarial settings. This paper improves FTPL algorithm for semi-bandit problems with best-of-both-worlds guarantees.
problem Optimizing regret in adversarial and stochastic m m m -set semi-bandit problems. method Extending FTPL with geometric resampling (GR) to m m m -set semi-bandits and analyzing its performance. result FTPL with Fréchet and Pareto distributions achieves O ( m d T ) O(\sqrt{mdT}) O ( m d T ) regret in adversarial setting and logarithmic regret in stochastic setting. We study a general online linear optimization problem(OLO). At each round, a subset of objects from a fixed universe of n n n objects is chosen, and a linear cost associated with the chosen subset is incurred. To measure the performance of our algorithms, we use the notion of regret which is the difference between the to…
CMOSS algorithm reduces regret in combinatorial semi-bandits with efficient computation.
problem Efficiently solving combinatorial semi-bandit problems with minimal regret.
method CMOSS algorithm achieves optimal regret bounds with minimal computational overhead.
result CMOSS achieves optimal regret bounds with minimal computational overhead.
Improved regret bound for adversarial MDPs with linear function approximation.
problem Learning in adversarial MDPs with changing loss functions and large state spaces.
method Two algorithms: refined FTRL with log-barrier regularizer and magnitude-reduced loss estimator.
result Achieved i l d e O ( K ) ilde{\mathcal O}(\sqrt K) i l d e O ( K ) regret, improving over i l d e O ( K 2 / 3 ) ilde{\mathcal O}(K^{2/3}) i l d e O ( K 2/3 ) . Capacity-Constrained Online Convex Optimization with Delayed Feedback
problem Online learning with delayed feedback under a hard capacity constraint
method Reduction to a delayed and weighted OCO problem using a scheduler
result First regret guarantees for capacity-constrained OCO under convex and strongly convex losses