Improved gap-dependent bounds for reinforcement learning with linear approximations.
problem Achieving nearly minimax-optimal performance with linear function approximation.
method Developed and analyzed the LSVI-UCB++ algorithm and its concurrent variant.
result First gap-dependent regret bound for nearly minimax-optimal algorithm LSVI-UCB++.
This paper improves Q-learning bounds using reference-advantage decomposition.
problem Improving Q-learning bounds in MDPs with positive suboptimality gaps.
method Develops a novel error decomposition framework to prove gap-dependent regret bounds.
result Establishes logarithmic gap-dependent regret bounds for Q-learning.
Study gap-dependent regret bounds for risk-sensitive RL.
problem Risk-sensitive reinforcement learning with entropic risk measure.
method Propose cascaded gaps to adapt to problem structures, derive regret bounds.
result Exponential improvement over existing bounds in appropriate settings.
New method reduces regret and communication costs in federated Q-learning.
problem Worst-case regret and communication cost bounds in federated Q-learning.
method Gap-dependent analysis leveraging MDP structures.
result Achieves log T \log T log T -type regret and communication cost bounds. Fine-grained gap-dependent regret bounds for reinforcement learning.
problem Achieving optimal regret bounds for reinforcement learning with suboptimality gaps.
method Developed novel analytical frameworks and refined algorithms for UCB-based and non-UCB-based reinforcement learning.
result Established the first fine-grained gap-dependent regret bounds for both UCB-based and non-UCB-based algorithms.
The paper analyzes Q-learning in 2-player Markov games and provides gap-dependent logarithmic regret bounds.
problem Analyzing the cumulative regret of Nash Q-learning in 2-player turn-based stochastic Markov games.
method Proposed gap-dependent logarithmic upper bounds for cumulative regret in episodic tabular setting and discounted game setting.
result The proposed bounds match theoretical lower bounds up to a logarithmic term.
Unified framework for corruption-robust linear bandits with optimal gap-dependent misspecification bounds.
problem Effective learning in linear bandits with corrupted rewards across different corruption models.
method Unified framework for analyzing strong and weak corruption, connection to gap-dependent misspecification, and specialized algorithm.
result Optimal bounds for gap-dependent misspecification in linear bandits.
Optimistic algorithms achieve logarithmic regret bounds for MDPs without diameter dependence.
problem Achieving logarithmic regret bounds for episodic MDPs without relying on diameter-like quantities.
method Novel 'clipped' regret decomposition applied to optimistic algorithms.
result Smooth interpolation between gap-dependent and minimax rates of convergence.
Improved bounds for adversarial bandits with variance analysis.
problem Optimizing decision-making in adversarial environments with varying gaps.
method First-order bounds, variance analysis, gap-dependent bounds for follow the regularized leader.
result Improved bounds for adversarial bandits with a factor of log(n)/log(log(n)) improvement.
New algorithm reduces MDP regret by accounting for state suboptimality gaps and variance.
problem Reducing regret in episodic MDPs with varying state suboptimality gaps.
method Introduced MVP algorithm with variance-aware gap-dependent regret bound.
result Achieved a variance-aware gap-dependent regret bound for MDPs.
A matroid is a notion of independence in combinatorial optimization which is closely related to computational efficiency. In particular, it is well known that the maximum of a constrained modular function can be found greedily if and only if the constraints are associated with a matroid. In this paper, we bring togethe…
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 ) . Adaptive smooth non-stationary bandits achieve optimal regret rates without knowing parameters.
problem Smooth non-stationary bandits with Hölder class rewards.
method Established optimal dynamic regret rate and adaptive algorithm.
result Optimal dynamic regret can be attained adaptively without knowing Hölder exponent and coefficient.
We consider the noisy power method algorithm, which has wide applications in machine learning and statistics, especially those related to principal component analysis (PCA) under resource (communication, memory or privacy) constraints. Existing analysis of the noisy power method shows an unsatisfactory dependency over …
Algorithm reduces regret in misspecified linear contextual bandits.
problem Misspecified linear contextual bandits with bounded misspecification.
method Data selection scheme for online regression, leveraging uncertainty.
result Regret bound of O ~ ( d 2 / Δ ) \tilde O(d^2/Δ) O ~ ( d 2 /Δ ) when ζ ≤ O ~ ( Δ / d ) ζ \leq \tilde O(Δ/\sqrt{d}) ζ ≤ O ~ ( Δ/ d ) . New algorithms minimize regret in streaming MAB with memory constraints.
problem Minimizing regret in single-pass streaming MAB with limited memory.
method Developed two algorithms with tight regret bounds for different memory sizes.
result Established tight gap-dependent regret bounds for streaming MAB.
Many important optimization problems, such as the minimum spanning tree and minimum-cost flow, can be solved optimally by a greedy method. In this work, we study a learning variant of these problems, where the model of the problem is unknown and has to be learned by interacting repeatedly with the environment in the ba…
New RL algorithms reduce costs for single-agent and federated learning.
problem Minimizing costs in RL and federated RL settings.
method Q-EarlySettled-LowCost and FedQ-EarlySettled-LowCost algorithms.
result First algorithms to achieve low burn-in and logarithmic switching costs.
A search engine usually outputs a list of K K K web pages. The user examines this list, from the first web page to the last, and chooses the first attractive page. This model of user behavior is known as the cascade model. In this paper, we propose cascading bandits, a learning variant of the cascade model where the obje…
A stochastic combinatorial semi-bandit is an online learning problem where at each step a learning agent chooses a subset of ground items subject to constraints, and then observes stochastic weights of these items and receives their sum as a payoff. In this paper, we close the problem of computationally and sample effi…
Improves policy optimization with polylog(T) regret bounds for stochastic losses.
problem Improves theoretical guarantees for policy optimization in stochastic settings.
method Leverages Tsallis and Shannon entropy regularizers for polylog(T) regret, and log-barrier regularizer for adversarial settings.
result Achieves a first-order polylog(T) regret bound for policy optimization in stochastic settings.
New algorithms identify best policies in discounted linear MDPs efficiently.
problem Identifying the best policy in discounted linear MDPs with limited samples.
method Derive lower bounds and devise simple yet near-optimal algorithms.
result Upper bound on sample complexity matches existing bounds.
KL-MS improves regret bounds for multi-armed bandits with bounded rewards.
problem Designing efficient exploration algorithms for multi-armed bandits with bounded rewards.
method Kullback-Leibler Maillard Sampling (KL-MS) for multi-armed bandits with bounded rewards.
result KL-MS achieves a worst-case regret bound of O ( μ ∗ ( 1 − μ ∗ ) K T ln K + K ln T ) O(\sqrt{μ^*(1-μ^*) K T \ln K} + K \ln T) O ( μ ∗ ( 1 − μ ∗ ) K T ln K + K ln T ) . RAVEN-UCB addresses non-stationary MAB problems with tighter regret bounds.
problem Non-stationary environments in multi-armed bandits.
method Combines variance-aware adaptation with three innovations: confidence bounds, adaptive control, and recursive updates.
result Achieves tighter regret bounds than UCB1 and UCB-V.
New algorithm reduces sample complexity for planning in MDPs.
problem Planning in MDPs with unknown transitions.
method MDP-GapE, a trajectory-based MCTS algorithm.
result Proves upper bound on sample complexity in terms of sub-optimality gaps.
PAC-Bayes bound for stable RNNs in time-series data.
problem Bounding generalization gap for stable RNNs in time-series data.
method Derived a PAC-Bayes bound with stability constraints for discrete-time non-linear dynamical systems, including stable RNNs.
result The bound converges to zero as dataset size increases, and does not grow with RNN steps.
Study online ranking in non-stationary environments with abrupt preference changes.
problem Online learning to rank in a non-stationary cascade model where user preferences change abruptly.
method Cascading non-stationary bandits, proposing CascadeDUCB and CascadeSWUCB algorithms.
result Upper and lower bounds on regret for cascading non-stationary bandits algorithms.
New algorithm achieves data-dependent regret bounds in MDPs with unknown transitions.
problem Achieving best-of-both-worlds guarantees with data-dependent regret bounds in MDPs with unknown transitions.
method Optimistic follow-the-regularized-leader algorithm with new optimistic Q-function estimators and transition bonus.
result First-order, second-order, and path-length bounds with polylog(T) regret in the stochastic regime.
First online learning to rank algorithm for broad click models.
problem Online learning to rank in stochastic click models.
method BatchRank, an algorithm for a broad class of click models.
result Derives a gap-dependent upper bound on the T T T -step regret of BatchRank. Unified framework for distributional regret in bandits and reinforcement learning.
problem Characterizing the distribution of regret in multi-armed bandits and reinforcement learning.
method Unified framework with a UCBVI-style algorithm and distributional regret bounds.
result Distributional regret bounds with optimal trade-offs between expected and distributional regret.
A search engine recommends to the user a list of web pages. The user examines this list, from the first page to the last, and clicks on all attractive pages until the user is satisfied. This behavior of the user can be described by the dependent click model (DCM). We propose DCM bandits, an online learning variant of t…
PHE adds pseudo-rewards to history to minimize regret in stochastic bandits.
problem Minimizing cumulative regret in stochastic multi-armed bandits.
method PHE algorithm that adds O ( t ) O(t) O ( t ) i.i.d. pseudo-rewards to history and pulls the best arm based on the perturbed history. result Near-optimal regret bounds derived for PHE.
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.
New bounds improve deep learning performance efficiently.
problem Improving generalization and robustness of deep learning models.
method Deriving four provable upper bounds on spectral norm of convolution layers, differentiable and efficient.
result Minimum of four bounds is a tight, differentiable and efficient upper bound on spectral norm.
Improved reinforcement learning for episodes with varying action sets.
problem Reinforcement learning with context-dependent action sets.
method Extends MVP algorithm to handle adversarial and stochastic contexts.
result Established minimax regret bounds of O ( S A H 3 K log L ) O(\sqrt{SAH^3K\log L}) O ( S A H 3 K log L ) for adversarial contexts. New method identifies best interventions with limited resources.
problem Identifying best soft interventions with budget constraints.
method Best arm identification bandit problem with information leakage.
result First gap-dependent error and simple regret bounds.
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.
The paper tackles resource allocation for arms with unknown and random rewards, achieving optimal regret bounds.
problem Allocating resources on arms with unknown and random rewards.
method Developed two algorithms with optimal regret bounds for b ∈ [ 0 , 1 ] b \in [0,1] b ∈ [ 0 , 1 ] , demonstrating a phase transition at b = 1 / 2 b=1/2 b = 1/2 . result Achieved optimal gap-dependent and gap-independent regret bounds for b ∈ [ 0 , 1 ] b \in [0,1] b ∈ [ 0 , 1 ] . Improved UCB and Thompson Sampling policies for CMAB with probabilistically triggered arms achieve bounded regret.
problem Combinatorial multi-armed bandit problem with probabilistically triggered arms.
method Upper Confidence Bound (UCB) policies and Combinatorial Thompson Sampling (CTS).
result CUCB- κ κ κ and CTS achieve O ( T ) O(\sqrt{T}) O ( T ) gap-independent regret. 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.
The paper tackles fair sequential decision making with biased linear bandit feedback.
problem Fair sequential decision making with biased linear bandit feedback.
method Phased elimination algorithm to correct unfair evaluations, establishing upper bounds on regret.
result The worst-case regret is smaller than O ( κ ∗ 1 / 3 log ( T ) 1 / 3 T 2 / 3 ) \mathcal{O}(κ_*^{1/3}\log(T)^{1/3}T^{2/3}) O ( κ ∗ 1/3 log ( T ) 1/3 T 2/3 ) . 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.
Logarithmic regret achieved in RL with linear function approximation.
problem Achieving logarithmic regret in reinforcement learning with linear function approximation.
method LSVI-UCB for linear MDP assumption, UCRL-VTR for linear mixture MDP assumption.
result Logarithmic regret bounds established for RL with linear function approximation.
Algorithm optimizes multi-player learning with noisy rewards without direct communication.
problem Cooperative multi-player learning with noisy rewards and no communication.
method Upper and lower confidence bounds algorithm for optimal action selection.
result Achieves logarithmic O ( log T Δ a ) O(\frac{\log T}{Δ_{\bm{a}}}) O ( Δ a l o g T ) and O ( T log T ) O(\sqrt{T\log T}) O ( T log T ) regret. 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. New policy optimizes product assortment in the presence of unpredictable customers.
problem Optimizing product assortment in the presence of outlier customers.
method Developed a robust online assortment optimization policy using an active elimination strategy.
result Established upper and lower bounds on regret, showing optimality up to logarithmic factor in T T T . Local gaps in Ricci shrinkers depend only on dimension.
problem Understanding local properties of Ricci shrinkers.
method Proved local versions of Ricci curvature and entropy gap theorems.
result Local gaps depend only on dimension, not global entropy.
New method for identifying best designs in vector optimization with uncertain feedback.
problem Optimizing vector-valued outcomes with uncertain preferences.
method Stochastic bandit feedback, polyhedral ordering cone, ( ε , δ ε,δ ε , δ )-PAC Pareto set identification. result Sample complexity characterized and matched by the naïve elimination algorithm.