The paper explores dynamic regret with switching cost in online decision making.
problem The relation between dynamic regret and switching cost in online decision making.
method Investigates two classic online settings: Online Algorithms (OA) and Online Convex Optimization (OCO). Provides a new theoretical analysis framework.
result The switching cost impacts dynamic regret differently in OA and has no impact in OCO.
Optimal switching regret for all segmentations in online convex optimisation.
problem Non-stationary online convex optimisation problems.
method Developed an efficient algorithm to achieve optimal switching regret on every possible segmentation.
result Achieved asymptotically optimal switching regret on every possible segmentation simultaneously.
SCaLE tackles dynamic regret in noisy bandit feedback with switching costs.
problem Unbounded metric movement costs in bandit online convex optimization.
method SCaLE algorithm for high-dimensional dynamic quadratic hitting costs and ℓ 2 \ell_2 ℓ 2 -norm switching costs, with spectral regret analysis. result First algorithm achieving sub-linear dynamic regret without hitting cost knowledge.
Paper analyzes minimax regret in constrained online convex optimization with limited switching opportunities.
problem Minimizing regret in online convex optimization with limited switching opportunities.
method Introduced fugal game relaxation and mini-batching algorithm to establish minimax regret bounds.
result Minimax regret of switching-constrained OCO is Θ(T / √K).
New RL algorithm reduces policy switching cost to loglog(T) with similar regret.
problem Low policy switching cost in real-life RL applications.
method Stage-wise exploration and adaptive policy elimination.
result Regret of O ( H S A log log T ) O(HSA \log\log T) O ( H S A log log T ) with O ( H S A log log T ) O(HSA \log\log T) O ( H S A log log T ) switching cost. Paper presents an efficient algorithm for linear MDP with low switching cost.
problem Large state space reinforcement learning problems with low switching cost.
method First algorithm for linear MDP with low switching cost, achieving near-optimal regret and switching cost.
result Regret bound of $\widetilde{O}\left(\sqrt{d^3H^4K}
ight)$ and near-optimal switching cost of $O\left(d H\log K
ight)$ .
This paper tackles near-optimal adversarial RL with switching costs, providing algorithms and matching lower bounds.
problem Adversarial RL with switching costs, where loss distribution can be non-stationary or adversarial.
method Developed novel switching-reduced algorithms with matching lower bounds for known and unknown transition functions.
result Achieved near-optimal performance in adversarial RL with switching costs, matching theoretical lower bounds.
New algorithm reduces switching costs in multinomial logit bandit problems.
problem Minimizing switching costs in multinomial logit bandit problems.
method Proposed AT-DUCB and FH-DUCB algorithms with low assortment switching costs.
result AT-DUCB and FH-DUCB algorithms achieve almost optimal minimax regret with low switching costs.
Study on revenue management with limited switches, achieving strong performance and reduced switch counts.
problem Resource-constrained dynamic pricing with limited switching constraints.
method Developed algorithms for blind network revenue management and bandits with knapsacks, achieving optimal regret rates.
result Optimal regret rates are fully characterized by a piecewise-constant function of the switching budget and resource constraints.
PCGS-TF uses a Transformer to adaptively control expert switching in non-stationary environments.
problem Static regret is insufficient for strictly online prediction in non-stationary settings.
method Policy-Controlled Generalized Share (PCGS) with a Transformer as an update controller.
result PCGS-TF achieves the lowest dynamic regret in non-stationary families and expert pools.
We consider the classical stochastic multi-armed bandit problem with a constraint that limits the total cost incurred by switching between actions to be no larger than a given switching budget. For this problem, we prove matching upper and lower bounds on the optimal (i.e., minimax) regret, and provide efficient rate-o…
Algorithm for bandits with switching costs achieves optimal regret bounds.
problem Optimal regret bounds for stochastic and adversarial bandits with switching costs.
method Adaptation of Tsallis-INF algorithm with no prior knowledge of regime or time horizon.
result Achieves minimax optimal regret bounds in various settings.
New algorithm tackles non-stationary combinatorial semi-bandit problems with optimal regret bounds.
problem Non-stationary combinatorial semi-bandit problems in switching and dynamic environments.
method Developed algorithms for both switching and dynamic cases, achieving nearly optimal regret bounds.
result Achieved nearly optimal regret bounds in both switching and dynamic cases.
New algorithm reduces switching costs in RL beyond linear MDPs.
problem Costly policy switching in reinforcement learning.
method ELEANOR-LowSwitching algorithm for linear Bellman-complete MDPs.
result Achieves near-optimal regret with logarithmic switching cost.
The paper improves competitive and dynamic regret bounds for smoothed online learning.
problem Smoothed online learning with hitting and switching costs.
method Optimization problems to minimize hitting cost, dynamic regret modification of existing algorithms.
result Improved competitive and dynamic regret bounds for various function classes.
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 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.
We take initial steps in studying PAC-MDP algorithms with limited adaptivity, that is, algorithms that change its exploration policy as infrequently as possible during regret minimization. This is motivated by the difficulty of running fully adaptive algorithms in real-world applications (such as medical domains), and …
We study online learning when partial feedback information is provided following every action of the learning process, and the learner incurs switching costs for changing his actions. In this setting, the feedback information system can be represented by a graph, and previous works studied the expected regret of the le…
Efficient algorithms for online convex optimization with limited switching decisions.
problem Online convex optimization with limited switching decisions.
method Presented computationally efficient algorithms for both general and strongly convex losses.
result Regret bounds of O ( T / S ) O(T/S) O ( T / S ) for general convex losses and O ~ ( T / S 2 ) \widetilde O(T/S^2) O ( T / S 2 ) for strongly convex losses. We study the power of different types of adaptive (nonoblivious) adversaries in the setting of prediction with expert advice, under both full-information and bandit feedback. We measure the player's performance using a new notion of regret, also known as policy regret, which better captures the adversary's adaptiveness…
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. Efficient RL algorithms for linear function approximation with limited adaptivity constraints.
problem Limited adaptivity in reinforcement learning with linear function approximation.
method Proposed two efficient online RL algorithms for episodic linear Markov decision processes under batch learning and rare policy switch models.
result Achieved efficient regret bounds for both batch learning and rare policy switch models, with substantial reduction in adaptivity.
New algorithm minimizes cumulative loss in dynamic linear bandits without prior knowledge of comparator switches.
problem Minimizing cumulative loss in dynamic linear bandits with unknown number of switches.
method Combining several bandit algorithms to adapt to unknown number of switches without prior knowledge.
result First algorithm achieving optimal regret guarantee of O ( d ( 1 + S T ) T ) \mathcal{O}\big(\sqrt{d(1+S_T) T}\big) O ( d ( 1 + S T ) T ) up to poly-logarithmic terms. New algorithm reduces decision switching in dynamic environments.
problem Online learning with memory and non-stationary environments.
method Dynamic policy regret, novel ensemble approach, meta-base decomposition.
result Proves optimal dynamic policy regret for memory length, non-stationarity, and time horizon.
Algorithm learns to switch control among agents in a team.
problem Learning to switch control among reinforcement learning agents.
method 2-layer Markov decision process, upper confidence bounds, shared confidence bounds.
result Sublinear total regret with shared confidence bounds.
New algorithms tackle adversarial combinatorial bandits with switching costs.
problem Adversarial combinatorial bandits with switching costs.
method Design algorithms operating in batches to restrict switches, proving lower bounds and achieving upper bounds on regret.
result Achieved upper bounds on regret for both bandit and semi-bandit feedback settings.
LaMBO optimizes modular systems with switching costs, achieving better results than existing methods.
problem Optimizing systems with costly variable updates in a sequence of modules.
method Lazy Modular Bayesian Optimization (LaMBO) that minimizes switching costs.
result LaMBO achieves vanishing regret and improves over existing cost-aware Bayesian optimization algorithms.
OMGD algorithm optimizes online convex optimization with switching costs and delayed gradients.
problem Optimizing online convex optimization with switching costs and delayed gradients.
method Proposed an online multiple gradient descent (OMGD) algorithm for quadratic and linear switching costs.
result OMGD achieves optimal dynamic regret in the limited information setting.
We study the adversarial multi-armed bandit problem where partial observations are available and where, in addition to the loss incurred for each action, a \emph{switching cost} is incurred for shifting to a new action. All previously known results incur a factor proportional to the independence number of the feedback …
New algorithm achieves both static and dynamic regret optimally against an oblivious adversary for deterministic losses.
problem Achieving optimal static and dynamic regret simultaneously in adversarial bandits.
method Extends impossibility result to deterministic losses, uses negative static regret and Blackwell approachability.
result First algorithm achieving optimal static and dynamic regret simultaneously against an oblivious adversary.
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.
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.
We consider online algorithms under both the competitive ratio criteria and the regret minimization one. Our main goal is to build a unified methodology that would be able to guarantee both criteria simultaneously. For a general class of online algorithms, namely any Metrical Task System (MTS), we show that one can sim…
Two algorithms achieve optimal regret with limited adaptivity in multinomial logistic bandits.
problem Achieving optimal regret with limited adaptivity in multinomial logistic bandits.
method Presented two algorithms, B-MNL-CB and RS-MNL, for batched and rarely-switching paradigms.
result Achieved i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) regret with limited adaptivity. 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.
Efficiently optimize GPs by reusing candidate solutions multiple times.
problem High computational cost of Gaussian process optimization due to unique historical points.
method Sticking to a candidate solution for multiple evaluation steps and limiting switches.
result Improved efficiency and practicality of Gaussian process optimization algorithms.
New algorithm reduces RL complexity with low switching costs.
problem Exploration-exploitation dilemma in RL with complex models.
method Monotonic Q-Learning with Upper Confidence Bound (MQL-UCB) for RL with general function approximation.
result Achieves minimax optimal regret of O ( d H K ) O(d\sqrt{HK}) O ( d H K ) and near-optimal policy switching cost. New method tracks significant arm switches to improve bandit algorithms.
problem Adaptive procedures for bandits with unknown changes in reward distribution.
method Proposes a new notion of significant shift to count severe changes.
result Achieves faster rates than previous methods, especially when few changes are severe.
We propose the first reduction-based approach to obtaining long-term memory guarantees for online learning in the sense of Bousquet and Warmuth, 2002, by reducing the problem to achieving typical switching regret. Specifically, for the classical expert problem with K K K actions and T T T rounds, using our framework we dev…
Online learning algorithms are designed to learn even when their input is generated by an adversary. The widely-accepted formal definition of an online algorithm's ability to learn is the game-theoretic notion of regret. We argue that the standard definition of regret becomes inadequate if the adversary is allowed to a…
Study on adaptivity constraints in linear contextual bandits with optimal design.
problem Impact of adaptivity constraints on linear contextual bandits.
method Two models of limited adaptivity: batch learning and rare policy switches. Proposed distributional optimal design.
result Achieves minimax-optimal regret with optimal number of policy switches and batches.
New algorithms for multitask learning with long-term memory.
problem Learning from tasks partitioned into unknown segments with associated hypotheses.
method Online multitask learning algorithms exploiting segmentation and hypothesis association.
result Regret bounds and efficient algorithms for various hypothesis classes.
UCB-Advantage learns MDPs with O ( H 2 S A T ) O(\sqrt{H^2SAT}) O ( H 2 S A T ) regret.
problem Model-free reinforcement learning in finite-horizon MDPs.
method Reference-Advantage decomposition for low regret.
result Achieves i l d e O ( H 2 S A T ) ilde{O}(\sqrt{H^2SAT}) i l d e O ( H 2 S A T ) regret, matching best known bounds. New algorithm minimizes expert selection regret in partial bandit feedback.
problem Minimizing expert selection regret in partial bandit feedback.
method Develops a sequential minimax optimal algorithm for a generalized partial monitoring setting.
result Second order regret bounds against a general expert selection sequence.
We consider the exploration-exploitation tradeoff in linear quadratic (LQ) control problems, where the state dynamics is linear and the cost function is quadratic in states and controls. We analyze the regret of Thompson sampling (TS) (a.k.a. posterior-sampling for reinforcement learning) in the frequentist setting, i.…
New private algorithms for online learning improve regret in high privacy regimes.
problem Private online learning from experts and convex optimization.
method Transformed lazy algorithms for differential privacy.
result Improved regret bounds for DP-OPE and DP-OCO.
To deal with changing environments, a new performance measure -- adaptive regret, defined as the maximum static regret over any interval, was proposed in online learning. Under the setting of online convex optimization, several algorithms have been successfully developed to minimize the adaptive regret. However, existi…