Paper explores rate-preserving reductions between Blackwell approachability and no-regret learning.
problem Tackles rate-preserving reductions between Blackwell approachability and no-regret learning.
method Studies fine-grained reductions and optimal rates of convergence.
result Shows that rate-preserving reductions do not always hold, but provides conditions for when they do.
Reduces dynamic regret to static problem in RKHS.
problem Minimizing cumulative loss in online convex optimization.
method Reduces dynamic regret to static regret problem in RKHS.
result Optimal dynamic regret guarantees for linear losses and new bounds for exp-concave and improper linear regression.
Online learning is a powerful tool for analyzing iterative algorithms. However, the classic adversarial setup sometimes fails to capture certain regularity in online problems in practice. Motivated by this, we establish a new setup, called Continuous Online Learning (COL), where the gradient of online loss function cha…
Unified approach for non-stationary linear bandits with dynamic regret.
problem Non-stationary linear bandits with round-specific feasible actions and drifting reward models.
method Unified misspecification-reduction viewpoint, restarting algorithms with misspecification-dependent regret guarantees.
result Optimal \(T^{2/3}P_T^{1/3}\) dynamic-regret dependence for both linear bandits and contextual linear bandits.
We show how to reduce the process of predicting general order statistics (and the median in particular) to solving classification. The accompanying theoretical statement shows that the regret of the classifier bounds the regret of the quantile regression under a quantile loss. We also test this reduction empirically ag…
Boosts weak online learners to strong ones with sublinear regret.
problem Online learning agnostic setting without strong guarantees.
method Reduction to online convex optimization, boosting via marginally-better-than-trivial regret guarantees.
result First agnostic online boosting algorithm with sublinear regret.
We introduce several new black-box reductions that significantly improve the design of adaptive and parameter-free online learning algorithms by simplifying analysis, improving regret guarantees, and sometimes even improving runtime. We reduce parameter-free online learning to online exp-concave optimization, we reduce…
Paper proposes FedQ-Advantage for federated Q-learning with near-optimal regret and low communication cost.
problem Near-optimal federated Q-learning with low communication cost.
method Reference-advantage decomposition for variance reduction, synchronization between agents and server, policy update.
result Achieves almost optimal regret and near-linear regret speedup compared to single-agent learning.
A method to minimize regret in multi-agent control systems with adversarial disturbances.
problem Optimal control of dynamical systems with adversarial disturbances and multiple agents.
method Reduction from online convex optimization to a distributed algorithm for multi-agent control.
result The resulting distributed algorithm has low regret relative to the optimal precomputed joint policy.
We present a reduction from reinforcement learning (RL) to no-regret online learning based on the saddle-point formulation of RL, by which "any" online algorithm with sublinear regret can generate policies with provable performance guarantees. This new perspective decouples the RL problem into two parts: regret minimiz…
New approach optimizes policies in adversarial MDPs using adversarial learning.
problem Optimizing policies in adversarial Markov decision processes.
method Adversarial learning on advantage functions, extending previous reductions.
result Stronger regret criteria and performance guarantees for policy optimization.
New algorithm learns optimal policies with minimal memory and time.
problem Learning optimal policies in discounted MDPs with short burn-in time.
method Variance reduction and adaptive policy switching.
result First regret-optimal model-free algorithm with low burn-in time.
Optimal algorithm for LQR control with improved regret bound.
problem Nonstochastic control with quadratic losses (LQR control).
method Online algorithm with optimal dynamic regret of i l d e O ( e x t m a x { n 1 / 3 T V ( M 1 : n ) 2 / 3 , 1 } ) ilde{O}( ext{max}\{n^{1/3} \mathcal{TV}(M_{1:n})^{2/3}, 1\}) i l d e O ( e x t ma x { n 1/3 TV ( M 1 : n ) 2/3 , 1 }) . result Improves the best known rate of i l d e O ( n ( T V ( M 1 : n ) + 1 ) ) ilde{O}(\sqrt{n (\mathcal{TV}(M_{1:n})+1)} ) i l d e O ( n ( TV ( M 1 : n ) + 1 ) ) for general convex losses. Bandits with Knapsacks (BwK) is a general model for multi-armed bandits under supply/budget constraints. While worst-case regret bounds for BwK are well-understood, we present three results that go beyond the worst-case perspective. First, we provide upper and lower bounds which amount to a full characterization for lo…
New RL algorithm reduces sample complexity for optimal learning.
problem Achieving optimal learning with minimal samples in RL.
method Early-settled variance reduction method with Q-learning sequences.
result Near-optimal regret achieved with sample size S A p o l y ( H ) SA\,\mathrm{poly}(H) S A poly ( H ) . Most bandit algorithm designs are purely theoretical. Therefore, they have strong regret guarantees, but also are often too conservative in practice. In this work, we pioneer the idea of algorithm design by minimizing the empirical Bayes regret, the average regret over problem instances sampled from a known distributio…
IDS improves sparse linear bandits by balancing information and regret.
problem Sparse linear bandits in high-dimensional decision-making.
method Information-directed sampling (IDS) with Bayesian regret bounds and empirical Bayesian sparse posterior sampling.
result IDS nearly matches existing lower bounds and significantly reduces regret.
We study adaptive regret bounds in terms of the variation of the losses (the so-called path-length bounds) for both multi-armed bandit and more generally linear bandit. We first show that the seemingly suboptimal path-length bound of (Wei and Luo, 2018) is in fact not improvable for adaptive adversary. Despite this neg…
A new algorithm reduces regret in high-dimensional online learning problems.
problem High-dimensional covariates with unknown reward function.
method BV-LASSO algorithm incorporating binning and voting for nonparametric variable selection.
result Achieves optimal regret i l d e O ( T ( d x ∗ + d y + 1 ) / ( d x ∗ + d y + 2 ) ) ilde{O}(T^{(d_x^*+d_y+1)/(d_x^*+d_y+2)}) i l d e O ( T ( d x ∗ + d y + 1 ) / ( d x ∗ + d y + 2 ) ) . Efficient methods reduce projections in non-stationary online learning.
problem Optimizing dynamic and adaptive regret in non-stationary online learning environments.
method Presented efficient methods reducing the number of projections per round from O ( log T ) O(\log T) O ( log T ) to 1 1 1 . result Reduced number of projections per round from O ( log T ) O(\log T) O ( log T ) to 1 1 1 for optimizing dynamic and adaptive regret. Sequential prediction problems such as imitation learning, where future observations depend on previous predictions (actions), violate the common i.i.d. assumptions made in statistical learning. This leads to poor performance in theory and often in practice. Some recent approaches provide stronger guarantees in this se…
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.
Study online linear regression with paid noise reduction.
problem Online linear regression with noisy features and the ability to pay for reduced noise.
method Analyzes regret against optimal predictor, uses matrix martingale concentration.
result Optimal regret rates for known and unknown noise covariance.
New approach turns optimal stationary RL into non-stationary RL without prior knowledge.
problem Optimal RL in non-stationary environments without prior knowledge of non-stationarity.
method Black-box reduction of optimal stationary RL algorithms to non-stationary RL.
result Achieves optimal dynamic regret bounds in various RL settings.
Develops a new method for online conformal prediction without manual tuning.
problem Achieving long-run 1 − α 1-α 1 − α coverage for arbitrary data streams in an informative manner. method Linearized regret theory and universal portfolio algorithms.
result Strong finite-time bounds on miscoverage for UP-OCP, outperforming prior methods.
This work improves online regression and contextual bandits using neural networks.
problem Improving online regression and contextual bandits using neural networks.
method Investigates neural networks for online regression, showing O ( log T ) \mathcal{O}(\log T) O ( log T ) regret for almost convex losses and KL loss. result Shows i l d e O ( K L ∗ + K ) ilde{\mathcal{O}}(\sqrt{KL^*} + K) i l d e O ( K L ∗ + K ) regret for NeuCB, outperforming existing algorithms. Decentralized optimization on dynamic manifolds with improved regret bound.
problem Optimizing on nonstationary Riemannian manifolds in decentralized systems.
method Decentralized projected Riemannian gradient descent with weighted Frechet mean consensus.
result Achieved dynamic regret bound of O ( T ( 1 + P T ) / ( 1 − σ 2 ( W ) ) ) {\cal O}(\sqrt{T(1+P_T)}/\sqrt{(1-σ_2(W))}) O ( T ( 1 + P T ) / ( 1 − σ 2 ( W )) ) . New algorithm for fair ranking in contextual bandits with concave rewards.
problem Fair ranking in recommendation systems.
method Geometric interpretation of CBCR as optimization, Frank-Wolfe analyses.
result First algorithm with provably vanishing regret for CBCR.
New method tackles online DR-submodular maximization with improved regret guarantees.
problem Online maximization of non-monotone DR-submodular functions over down-closed convex sets.
method 1/e-linearization through exponential reparametrization, surrogate potential, and reduction to online linear optimization.
result Achieves O ( T 1 / 2 ) O(T^{1/2}) O ( T 1/2 ) static regret with single gradient query per round, improving state of the art. Improved UCB algorithm for diversity in bandits with lower bounds.
problem Improving diversity in bandit-based recommendations.
method Designing a UCB algorithm exploiting the specific structure of the problem.
result The UCB algorithm achieves bounded distribution-dependent regret under certain conditions.
Study on optimal rates for sequential probability assignment using smoothed analysis.
problem Optimal rates for sequential probability assignment under smoothed adversaries.
method General-purpose reduction from minimax rates to transductive learning, development of an efficient algorithm using MLE oracle.
result Optimal (logarithmic) fast rates for parametric and finite VC dimension classes, sublinear regret for general classes.
Proposes a method to learn policies from offline data with reduced bias.
problem Learning policies from offline data with reduced bias and complexity constraints.
method Cross-fitted debiasing device for policy learning from offline data.
result Achieves N \sqrt N N regret for complex policy classes with a product-of-errors nuisance remainder. Transforms offline algorithms to online with low regret in random order model.
problem Developing online algorithms with low approximate regret from offline approximation algorithms.
method General reduction theorem and coreset construction method.
result Achieves polylogarithmic ε-approximate regret for various online problems.
Optimistic Thompson Sampling reduces regret in unknown multi-player games.
problem Navigating uncertainty in unknown multi-player games with strategic decision-making.
method Introduces Thompson Sampling algorithms that exploit opponents' actions and reward structures.
result Achieves over tenfold improvements in experimental budgets with logarithmic regret bound.
New algorithms reduce forecasting errors by leveraging optimistic learning and hinting.
problem Real-time climate forecasting with delayed feedback.
method Developed optimistic online learning algorithms that reduce regret under delayed feedback.
result Optimistic learning algorithms achieve optimal regret guarantees under delayed feedback.
A new metric, Weighted Regret, unifies FDR and power evaluation in online multiple testing.
problem The asymmetric costs of false positives and false negatives in automated pipelines.
method Introducing Weighted Regret and Decoupled-OMT (DOMT) to unify FDR and power evaluation.
result DOMT achieves an order-optimal sublinear mitigation of threshold depletion in bursty environments.
New algorithm reduces dynamic regret in time-varying movement costs.
problem Dynamic regret in online convex optimization with time-varying movement costs.
method Introduced a novel algorithm for time-varying movement costs, achieving comparator-adaptive dynamic regret bound.
result Established first comparator-adaptive dynamic regret bound of O ~ ( ( M 2 + M P T ) ( T + ∑ t λ t ) ) \widetilde{\mathcal{O}}(\sqrt{(M^2+MP_T)(T+\sum_t λ_t)}) O ( ( M 2 + M P T ) ( T + ∑ t λ t ) ) . Enhances RL with function approximation, improving regret bounds.
problem Improving exploration in reinforcement learning with function approximation.
method Prior-dependent Bayesian regret bound for PSRL with linear mixture MDPs, using value-targeted model learning and variance reduction.
result Established an upper bound of O ( d H 3 T log T ) {\mathcal{O}}(d\sqrt{H^3 T \log T}) O ( d H 3 T log T ) for PSRL. Improved GP bandit algorithms for noiseless, varying noise, and RKHS norms.
problem Minimizing regret in Gaussian process bandits with unknown reward functions.
method New upper bound on maximum posterior variance, refined MVR and PE algorithms.
result Optimal regret bounds for noiseless, varying noise, and RKHS norms.
New method uses correlated auxiliary feedback to reduce regret in parameterized bandits.
problem Reducing regret in parameterized bandits with correlated auxiliary feedback.
method Develops a reward estimator using auxiliary feedback with tight confidence bounds.
result Shows significant reduction in regret compared to standard methods.
Study sparsity benefits in infinite feature contextual bandits.
problem Minimizing regret in infinite feature contextual bandits.
method Novel reduction to multi-armed bandits, Feel-Good Thompson Sampling algorithm.
result Regret bounds match lower bounds up to logarithmic factors, logarithmic dependence on effective features.
Online learning is a powerful tool for analyzing iterative algorithms. However, the classic adversarial setup sometimes fails to capture certain regularity in online problems in practice. Motivated by this, we establish a new setup, called Continuous Online Learning (COL), where the gradient of online loss function cha…
New algorithm reduces regret in multi-agent bandits with malicious agents.
problem Collaboration between honest and malicious agents in multi-armed bandits.
method Dynamic reduction of communication with malicious agents, learning who is malicious.
result Algorithm reduces regret even with a single malicious agent, assuming m m m is small compared to K K K . New reinforcement learning algorithm achieves instance-optimal sample complexity.
problem Achieving low regret and identifying optimal policies in reinforcement learning.
method A novel planning-based algorithm that explicitly accounts for state visitation distributions.
result The proposed algorithm attains nearly minimax optimal sample complexity, improving over worst-case bounds.
New algorithms achieve no-regret learning even with adversarial transitions and losses.
problem No-regret learning impossible with adversarial transitions and losses.
method Developed algorithms for adversarial Markov Decision Processes with smooth regret increase.
result Achieved O ~ ( T + C e x t s f P ) \widetilde{O}(\sqrt{T} + C^{ extsf{P}}) O ( T + C e x t s f P ) regret, with C e x t s f P C^{ extsf{P}} C e x t s f P measuring adversarial transition function. Algorithm learns interference network and optimizes treatment allocation for unknown network effects.
problem Adaptive experimentation under unknown network interference.
method Thompson sampling algorithm with Gibbs sampler for joint learning of interference network and treatment allocation.
result Proves a Bayesian regret bound and achieves sublinear regret in real-world applications.
We introduce CSE for MLSF games and devise online learning algorithms for achieving no-external Stackelberg-regret.
problem Learning equilibrium in leader-follower games with noisy bandit feedback.
method Proposed Correlated Stackelberg Equilibrium (CSE) and online learning algorithms balancing exploration and exploitation.
result Achieves no-external Stackelberg-regret, converging to approximate CSE.
We study an online decision making problem where on each round a learner chooses a list of items based on some side information, receives a scalar feedback value for each individual item, and a reward that is linearly related to this feedback. These problems, known as contextual semibandits, arise in crowdsourcing, rec…