Bandit algorithms struggle with consistent performance and robustness.
problem Achieving consistent and robust performance in stochastic multi-armed bandit settings.
method Analyzing regret minimization trade-offs and proposing distribution-oblivious algorithms.
result Logarithmic regret is inconsistent and super-logarithmic regret is necessary for consistent learning.
New bounds on minimax regret for sequential probability assignment using logarithmic loss.
problem Minimizing regret in sequential probability assignment against arbitrary experts.
method Using self-concordance property of logarithmic loss to derive tight bounds.
result Tight bounds on minimax regret for various expert classes.
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 proof for various bandit algorithms with logarithmic regret.
problem Achieving logarithmic regret in stochastic bandit algorithms.
method Minimal high-probability concentration condition and two deterministic lemmas.
result Unified proofs for classical and contemporary bandit algorithms.
Logarithmic regret for continuous-time reinforcement learning.
problem Continuous-time Markov decision processes with unknown transition probabilities and holding times.
method Upper confidence reinforcement learning, mean holding time estimation, stochastic comparison of point processes.
result Logarithmic regret bound achieved in finite time.
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.
Logarithmic regret achieved in Q-learning with positive gap.
problem Achieving logarithmic cumulative regret in Q-learning with positive sub-optimality gap.
method Optimistic Q-learning with logarithmic regret bound.
result Logarithmic cumulative regret bound proven for optimistic Q-learning.
Near-logarithmic regret per switch achieved for mixable/exp-concave losses.
problem Online optimization of mixable loss functions with dynamic environments.
method Online mixture framework using static solvers and hyper-expert creations.
result Near-logarithmic regret per switch with sub-polynomial complexity.
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.
Logarithmic regret achieved in continuous-time linear-quadratic reinforcement learning.
problem Optimizing control actions in unknown continuous-time systems over a finite time horizon.
method Least-squares algorithm based on continuous-time observations and controls, with perturbation analysis and parameter estimation error analysis.
result Logarithmic regret bound of order O ( ( ln M ) ( ln ln M ) ) O((\ln M)(\ln\ln M)) O (( ln M ) ( ln ln M )) . We develop a new theoretical framework, the \emph{envelope complexity}, to analyze the minimax regret with logarithmic loss functions and derive a Bayesian predictor that adaptively achieves the minimax regret over high-dimensional ℓ 1 \ell_1 ℓ 1 -balls within a factor of two. The prior is newly derived for achieving the mini…
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.
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.
We introduce a new algorithm for online linear-quadratic control in a known system subject to adversarial disturbances. Existing regret bounds for this setting scale as T \sqrt{T} T unless strong stochastic assumptions are imposed on the disturbance process. We give the first algorithm with logarithmic regret for arbitra…
We study the problem of regret minimization for distributed bandits learning, in which M M M agents work collaboratively to minimize their total regret under the coordination of a central server. Our goal is to design communication protocols with near-optimal regret and little communication cost, which is measured by the…
Logarithmic regret strategies for safe multi-armed bandits with safety risk constraints.
problem Maximizing reward while avoiding unsafe arms under safety risk constraints.
method Doubly optimistic strategies with pseudo-regret formulation.
result Logarithmic regret bounds for safe multi-armed bandits.
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.
This paper establishes that optimistic algorithms attain gap-dependent and non-asymptotic logarithmic regret for episodic MDPs. In contrast to prior work, our bounds do not suffer a dependence on diameter-like quantities or ergodicity, and smoothly interpolate between the gap dependent logarithmic-regret, and the $\wid…
Paper analyzes and improves KL-regularized RL for LLMs with logarithmic regret.
problem Improving efficiency of RL fine-tuning for large language models.
method Optimism-based KL-regularized online contextual bandit algorithm with novel regret analysis.
result Achieves an O ( η log ( N R T ) ⋅ d R ) \mathcal{O}\big(η\log (N_{\mathcal R} T)\cdot d_{\mathcal R}\big) O ( η log ( N R T ) ⋅ d R ) logarithmic regret bound. We study the decades-old problem of online portfolio management and propose the first algorithm with logarithmic regret that is not based on Cover's Universal Portfolio algorithm and admits much faster implementation. Specifically Universal Portfolio enjoys optimal regret O ( N ln T ) \mathcal{O}(N\ln T) O ( N ln T ) for N N N financial instrum…
Oracle-efficient algorithms reduce combinatorial semi-bandit regret to logarithmic time.
problem Scalability issue in combinatorial semi-bandit problems due to high combinatorial optimization costs.
method Oracle-efficient frameworks that minimize oracle queries while maintaining tight regret guarantees.
result Achieved i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) regret with O ( log log T ) O(\log\log T) O ( log log T ) oracle queries for worst-case linear rewards. Algorithm achieves logarithmic regret with sublinear hints.
problem Online linear optimization with limited hints.
method Using logarithmic hints to improve regret from sqrt(T) to log(T).
result O(log T) regret with O(sqrt(T)) hints, and O(sqrt(T)) regret with o(sqrt(T)) hints.
Algorithm reduces regret in multi-player bandits with unknown collision rewards.
problem Reducing regret in multi-player multi-armed bandits with unknown collision rewards.
method Proposes an algorithm that combines a modified successive elimination strategy with a communication protocol to estimate suboptimality gaps and coordinate among players.
result Achieves logarithmic regret for the problem when collision reward is unknown.
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…
The problem of distributed learning and channel access is considered in a cognitive network with multiple secondary users. The availability statistics of the channels are initially unknown to the secondary users and are estimated using sensing decisions. There is no explicit information exchange or prior agreement amon…
Unified analysis of online optimization with self-concordant barriers, improving regret bounds.
problem Online convex optimization with specific loss functions.
method Online mirror descent with self-concordant barriers and logarithmic loss.
result Improved regret bounds for online portfolio selection and quantum state learning.
New algorithm reduces bandit problem's regret bound to logarithmic in dimension.
problem Sparse linear bandit problem with sparse reward structure.
method Proposes an algorithm that uses compatibility condition on optimal arm.
result Achieves regret bound of O(poly log dT) without additional diversity assumptions.
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.
A decentralized policy achieves logarithmic regret for multi-agent MAB problems with communication constraints.
problem Decentralized policy for multi-agent MAB problems with option availability and communication constraints.
method Upper Confidence Bound (UCB) algorithms with non-stationary stochastic communication protocol.
result Guaranteed logarithmic regret for non-fully connected spatial graphs with communication constraints.
Dynamic pricing improves DeFi lending efficiency by reducing regret to logarithmic levels.
problem Static pricing mechanisms in DeFi lending protocols lead to suboptimal welfare and revenue.
method Online learning model for static and dynamic pricing models in DeFi lending.
result Adaptive supply models achieve logarithmic regret, outperforming static models.
We consider the problem of learning in Linear Quadratic Control systems whose transition parameters are initially unknown. Recent results in this setting have demonstrated efficient learning algorithms with regret growing with the square root of the number of decision steps. We present new efficient algorithms that ach…
Algorithm minimizes regret in multi-criteria bandits with constraints.
problem Optimize primary attribute while respecting secondary constraints.
method Con-LCB algorithm that guarantees logarithmic regret and feasibility identification.
result Logarithmic regret and feasibility identification with high probability.
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.
New rule reduces exploration regret to logarithmic, improving bad episode handling.
problem Improving exploration regret in average reward MDPs.
method Replacing Doubling Trick with Vanishing Multiplicative rule in EVI-based algorithms.
result Regret is logarithmic under the new rule, significantly better than linear.
New method reduces multi-armed bandit regret to near-optimal levels.
problem Improving regret bounds for KL-regularized multi-armed bandits.
method Sharp analysis of KL-UCB with peeling argument.
result First high-probability regret bound with linear dependence on K.
New algorithms achieve logarithmic regret in KL-regularized Markov games.
problem Improving sample efficiency in game-theoretic settings with KL regularization.
method Developed OMG and SOMG algorithms for matrix and Markov games, using best response sampling and superoptimistic bonuses.
result Logarithmic regret in T T T that scales inversely with KL regularization strength β β β . 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.
New bounds for Bayesian bandits show prior improves performance.
problem Improving regret bounds for Bayesian bandits.
method Upper confidence bound algorithm with finite-time logarithmic regret bounds.
result Derives O ( c Δ log n ) O(c_Δ\log n) O ( c Δ log n ) and O ( c h log 2 n ) O(c_h \log^2 n) O ( c h log 2 n ) upper bounds for Bayesian bandits. 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.
Quantum RL algorithm achieves logarithmic regret for exploration.
problem Designing efficient quantum RL algorithms for exploration.
method UCRL-style quantum algorithm with lazy updating and quantum estimation.
result Proves O ( p o l y ( S , A , H , log T ) ) \mathcal{O}(\mathrm{poly}(S, A, H, \log T)) O ( poly ( S , A , H , log T )) worst-case regret. Algorithm learns expert weights to minimize regret in adversarial setting.
problem Learning to aggregate expert forecasts with no-regret guarantee in adversarial conditions.
method Online mirror descent algorithm for logarithmic pooling of expert forecasts.
result Achieves O ( T log T ) O(\sqrt{T} \log T) O ( T log T ) expected regret compared to best weights. A learning algorithm achieves logarithmic regret in a market making model.
problem Learning the price sensitivity parameter in a market making model.
method Maximum-likelihood estimator with regularization, based on HJB equation.
result Regret upper bound of order ln^2 T in expectation.
Study on regret minimization in deterministic MDPs.
problem Minimizing regret in deterministic reinforcement learning.
method Logarithmic regret lower bounds, leveraging graph theory and cycles.
result Explicitly quantifies the fundamental limit of performance achievable by any learning algorithm.
Greedy algorithm achieves sublinear regret for various distributions.
problem Efficient performance of greedy algorithms in linear contextual bandit problems.
method Introduced Local Anti-Concentration (LAC) condition to ensure sublinear regret.
result Greedy algorithm achieves O ( poly log T ) O(\operatorname{poly} \log T) O ( poly log T ) cumulative expected regret. 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.
Adaptive gradient methods have become recently very popular, in particular as they have been shown to be useful in the training of deep neural networks. In this paper we have analyzed RMSProp, originally proposed for the training of deep neural networks, in the context of online convex optimization and show T \sqrt{T} T -…
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 algorithm reduces regret for many bandit algorithms with logarithmic dependence on number of algorithms.
problem Combining and learning over a large set of adversarial bandit algorithms to track the best one.
method Proposes a new algorithm (CORRAL) with logarithmic regret dependence on the number of base algorithms.
result Achieves optimal switching regret for adversarial linear bandits over a d d d -dimensional ℓ p \ell_p ℓ p unit-ball.