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.
Regret minimization is a powerful tool for solving large-scale problems; it was recently used in breakthrough results for large-scale extensive-form game solving. This was achieved by composing simplex regret minimizers into an overall regret-minimization framework for extensive-form game strategy spaces. In this paper…
Optimal bounds on regret and constraint violation in adversarial COCO.
problem Minimizing regret and cumulative constraint violation in adversarial COCO.
method New surrogate loss function and Follow-the-Regularized-Leader/Online Gradient Descent.
result Achieved optimal O ( T ) O(\sqrt{T}) O ( T ) bounds on both regret and cumulative constraint violation. New algorithm reduces constraint violation to O ( T 1 / 3 ) O(T^{1/3}) O ( T 1/3 ) while maintaining O ( T ) O(\sqrt{T}) O ( T ) regret.
problem Minimizing static regret and cumulative constraint violation in constrained online convex optimization.
method Proposes an algorithm that achieves O ( T ) O(\sqrt{T}) O ( T ) regret and O ( T 1 / 3 ) O(T^{1/3}) O ( T 1/3 ) cumulative constraint violation. result Shows that O ( T 1 / 3 ) O(T^{1/3}) O ( T 1/3 ) cumulative constraint violation is achievable with O ( T ) O(\sqrt{T}) O ( T ) regret. LinConTS improves regret and constraint violations in probabilistic linearly constrained bandits.
problem Maximizing cumulative reward under probabilistic linear constraints.
method LinConTS, a Thompson Sampling-based algorithm for bandits with linear constraints.
result LinConTS achieves O(log T) regret and constraint violations for suboptimal arms.
Improved COCO algorithms with better constraint control.
problem Achieving small regret and constraint violation in online convex optimization.
method Simple projection-based algorithm leveraging self-contraction geometry.
result Exponential improvement in cumulative constraint violation for strongly convex losses.
The paper optimizes regret using covariance between costs and decisions.
problem Optimizing expected regret in decision-making problems.
method Developed derivative theory of covariance regret functional, derived Gâteaux derivative, and extended to constrained optimization.
result Gradient of covariance regret is the cost covariance matrix, with implications for portfolio optimization.
Optimizing rewards under budget constraints with correlated costs and rewards.
problem Maximizing total expected reward under a budget constraint on total cost with correlated and potentially heavy-tailed cost-reward pairs.
method Proposes algorithms exploiting correlation between cost and reward via linear minimum mean-square error estimation to achieve tight regret bounds.
result Achieves O ( log B ) O(\log B) O ( log B ) regret for a budget B > 0 B>0 B > 0 under certain moment conditions. New algorithm reduces regret and constraint violation in constrained bandit problems.
problem Optimizing under budget and stochastic constraints in resource-constrained settings.
method Lyapunov optimization methodology, t L y O n { t LyOn} t L y O n algorithm. result Achieves O ( K B log B ) O(\sqrt{K B\log B}) O ( K B log B ) regret and zero constraint-violation for large B B B . PDCA algorithm learns policies for RL with constraints using a primal-dual approach.
problem Offline constrained reinforcement learning with general function approximation.
method Primal-Dual-Critic Algorithm (PDCA) using a primal-dual approach.
result PDCA finds a near saddle point of the Lagrangian, nearly optimal for constrained RL.
New algorithm ensures consistent results in constrained MAB problems.
problem Achieving consistent results in constrained MAB problems.
method Developed replicable algorithms for constrained MAB problems using the optimism principle.
result Regret and constraint violation of replicable algorithms match those of non-replicable ones.
FMDP-BF algorithm improves RL in factored MDPs with exponential regret reduction.
problem Efficient reinforcement learning in factored MDPs with constrained RL.
method FMDP-BF algorithm leveraging factorization structure of FMDPs.
result FMDP-BF's regret is exponentially smaller than optimal algorithms for non-factored MDPs.
New algorithms minimize dynamic regret for strongly convex losses.
problem Minimizing dynamic regret for strongly convex losses.
method Developed Strongly Adaptive algorithms exploiting KKT conditions.
result Achieved near optimal dynamic regret of O ( d 1 / 3 n 1 / 3 e x t T V [ u 1 : n ] 2 / 3 ∨ d ) O(d^{1/3} n^{1/3} ext{TV}[u_{1:n}]^{2/3} \vee d) O ( d 1/3 n 1/3 e x t T V [ u 1 : n ] 2/3 ∨ d ) . Paper improves COCO problem, reducing constraint violation at the cost of slightly more regret.
problem Online Convex Optimization with adversarial constraints.
method Proposes new policies that trade off regret for reduced constraint violation.
result Achieves i l d e O ( d T + T β ) ilde{O}(\sqrt{dT}+ T^β) i l d e O ( d T + T β ) regret and i l d e O ( d T 1 − β ) ilde{O}(dT^{1-β}) i l d e O ( d T 1 − β ) CCV. Algorithm minimizes loss and constraint violations in online convex optimization with smooth penalties.
problem Minimizing loss and constraint violations in online convex optimization with smooth penalties.
method Projected gradient descent over a set around the current action.
result Both dynamic regret and constraint violation are bounded by the path-length.
A model for deciding which facts to remember in a lifelong learning scenario.
problem Deciding which facts to retain in limited memory from an endless stream of information.
method Mathematical model based on online learning framework, using multiplicative weights update algorithm with modifications.
result Design of an alternative scheme with close to optimal regret guarantees for memory-constrained lifelong learning.
Memory-limited learning tackles adversarial bandits with reduced storage.
problem Adversarial bandit problem with limited memory storage.
method Hierarchical learning policy with sublinear memory requirement.
result Established sublinear regret bounds for weak and shifting regrets.
A new test improves statistical inference in bandit algorithms without sacrificing adaptiveness.
problem Challenges in statistical inference for adaptive randomised experiments in bandits.
method An allocation probability test for Thompson Sampling without trading-off regret or requiring large sample sizes.
result Improves statistical inference in small samples, showing advantages in mental health experiments.
New framework for understanding adversarial and stochastic learning.
problem Understanding the continuum from adversarial to stochastic settings in online learning.
method Distributionally constrained adversaries framework.
result Characterization of learnable distribution classes for various function classes.
New algorithms control loss and constraints in uncertain, changing environments.
problem Adapting to adversarial constraints in uncertain, changing environments.
method Developed algorithms for constrained MAB problems with optimal rates of regret and positive constraint violation.
result Achieved optimal rates of regret and positive constraint violation under varying degrees of adversariality.
In recent years, constrained optimization has become increasingly relevant to the machine learning community, with applications including Neyman-Pearson classification, robust optimization, and fair machine learning. A natural approach to constrained optimization is to optimize the Lagrangian, but this is not guarantee…
We study the problem of switching-constrained online convex optimization (OCO), where the player has a limited number of opportunities to change her action. While the discrete analog of this online learning task has been studied extensively, previous work in the continuous setting has neither established the minimax ra…
Safe RL in linear systems achieves T \sqrt{T} T -regret.
problem Efficiently learning in safety-constrained online reinforcement learning.
method Study of linear quadratic regulator with safety constraints.
result First safe algorithm with i l d e O T ( T ) ilde{O}_T(\sqrt{T}) i l d e O T ( T ) -regret. The paper develops methods for time-varying constrained online convex optimization.
problem Time-varying loss and constraint functions in online convex optimization.
method Model-based augmented Lagrangian methods (MALM) for time-varying and delayed feedback.
result Sublinear regret and constraint violation for both time-varying and delayed feedback scenarios.
New algorithms for constrained online optimization with memory and predictions.
problem Control of constrained dynamical systems and scheduling with reconfiguration budgets.
method Proposed algorithms achieving sublinear regret and constraint violation under time-varying constraints, both with and without predictions.
result First algorithms achieving sublinear regret and constraint violation in constrained online optimization with memory.
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. Distributed Thompson sampling improves regret convergence in constrained communication networks.
problem Maximizing a black-box function with multi-agent Bayesian optimization under communication constraints.
method Distributed Thompson sampling using Gaussian processes, with theoretical bounds on regret convergence.
result Theoretical bounds on Bayesian average and simple regret depend on communication graph structure and are applicable in constrained networks.
Paper proposes algorithms to minimize both dynamic and adaptive regret simultaneously.
problem Traditional regret minimization algorithms are suboptimal for changing environments.
method Developed novel online algorithms to minimize dynamic and adaptive regret simultaneously.
result Proposed algorithms minimize dynamic and adaptive regret over any interval.
Agents collaborate to minimize regret while keeping costs under a threshold.
problem Collaborative multi-agent stochastic linear bandits with cost constraints.
method Safe distributed upper confidence bound algorithm (MA-OPLB) with accelerated consensus.
result Regret bound of order $ \mathcal{O}\left(\frac{d}{τ-c_0}\frac{\log(NT)^2}{\sqrt{N}}\sqrt{\frac{T}{\log(1/|λ_2|)}}
ight)$ .
We study contextual bandits with budget and time constraints, referred to as constrained contextual bandits.The time and budget constraints significantly complicate the exploration and exploitation tradeoff because they introduce complex coupling among contexts over time.Such coupling effects make it difficult to obtai…
New algorithm achieves optimal regret in average reward MDPs without prior bias information.
problem Achieving optimal regret in average reward MDPs with computational efficiency and without prior bias information.
method Projective Mitigated Extended Value Iteration (PMEVI) to compute bias-constrained optimal policies efficiently.
result First tractable algorithm with minimax optimal regret of O ~ ( s p ( h ∗ ) S A T ) \widetilde{\mathrm{O}}(\sqrt{\mathrm{sp}(h^*) S A T}) O ( sp ( h ∗ ) S A T ) . Optimal bidding strategy for multi-platform ad auctions under budget constraints.
problem Optimizing ad placements for budget-constrained advertisers across multiple platforms.
method Developed an optimal bidding strategy for non-incentive-compatible auctions with budget constraints.
result Maximized total utility across auctions while satisfying budget constraints in expectation.
Meta-learning control algorithm with finite-time guarantees for unknown systems.
problem Online control of unknown linear systems with constraints.
method Provable regret guarantees for an iterative control algorithm.
result Regret bounds of O ( T 3 / 4 ) O(T^{3/4}) O ( T 3/4 ) for controller cost and constraint violation. Paper proposes a model-free algorithm for CMDPs with long-term constraints, achieving optimal regret bounds.
problem Optimizing systems with long-term constraints where transition probabilities are unknown.
method Combines concepts from constrained optimization and Q-learning to propose an algorithm.
result Achieves optimal regret bounds for reward and constraint violation.
Algorithm optimizes constrained reinforcement learning with dual variables.
problem Minimizing convex functional subject to convex constraint in large state spaces.
method VPDPO algorithm using Lagrangian and Fenchel duality.
result Achieves sublinear regret and constraint violation, globally optimal policy.
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
New algorithm achieves sublinear regret in CMDPs without error cancellations.
problem Safety constraints in reinforcement learning with error cancellations.
method Model-based primal-dual algorithm for CMDPs with multiple constraints.
result Achieves sublinear regret without error cancellations.
New algorithm reduces regret in sequential decision-making problems.
problem Balancing exploration and exploitation in online sequential decision problems.
method Variational Bayesian optimistic sampling (VBOS) for optimizing policies.
result VBOS achieves i l d e O ( A T ) ilde O(\sqrt{AT}) i l d e O ( A T ) Bayesian regret for stochastic multi-armed bandits. New algorithm reduces regret in CMDPs without cancellation of errors.
problem Lagrangian approaches in CMDPs struggle with cancellation of errors.
method OptAug-CMDP, based on augmented Lagrangian method.
result Regret of i l d e O ( K ) ilde{O}(\sqrt{K}) i l d e O ( K ) for both objective and constraint violation. Dynamic pricing learns demand model from sparse product networks.
problem Minimizing revenue loss in a large network of products with unknown demand parameters.
method Combines optimism-in-the-face-of-uncertainty and PAC-Bayesian approaches.
result Achieves asymptotically optimal performance in terms of network size and time horizon.
New RL algorithm achieves sublinear regret and constraint violation without simulators.
problem Maximizing reward under utility constraints in large-scale systems.
method Model-free, simulator-free algorithm using LSVI-UCB with primal-dual optimization and soft-max policy.
result Achieves i l d e O ( d 3 H 3 T ) ilde{\mathcal{O}}(\sqrt{d^3H^3T}) i l d e O ( d 3 H 3 T ) regret and i l d e O ( d 3 H 3 T ) ilde{\mathcal{O}}(\sqrt{d^3H^3T}) i l d e O ( d 3 H 3 T ) constraint violation bounds. A dueling bandit problem with resource constraints is solved using EXP3.
problem Maximizing rewards in dueling bandits with resource constraints.
method EXP3 algorithm considering resource consumptions.
result Achieves $ ilde{\mathcal{O}}\left({\frac{OPT^{(b)}}{B}}K^{1/3}T^{2/3}
ight)$ regret.
Algorithm minimizes regret and converges to equilibria in Markov games.
problem Regret minimization and convergence to equilibria in general-sum Markov games under adversarial opponents.
method Decentralized algorithm that uses policy optimization and controls path length to achieve sublinear regret.
result Sublinear regret guarantees for convergence to correlated equilibrium in Markov games.
We consider regret minimization in repeated games with non-convex loss functions. Minimizing the standard notion of regret is computationally intractable. Thus, we define a natural notion of regret which permits efficient optimization and generalizes offline guarantees for convergence to an approximate local optimum. W…
The paper tackles best arm identification with minimal regret in experiments.
problem Identifying the best arm with minimal regret in experiments.
method Information-theoretic techniques and Double KL-UCB algorithm.
result Achieves asymptotic optimality in identifying the best arm with minimal regret.
New algorithms minimize simple and cumulative regret in contextual bandits.
problem Minimizing simple and cumulative regret in contextual bandit settings.
method Proposed new algorithms using conformal arm sets (CASs).
result Near-optimal minimax guarantees for simple regret and state-of-the-art guarantees for cumulative regret.
There are two variants of the classical multi-armed bandit (MAB) problem that have received considerable attention from machine learning researchers in recent years: contextual bandits and simple regret minimization. Contextual bandits are a sub-class of MABs where, at every time step, the learner has access to side in…
New algorithm minimizes worst-case regret in uncertain, time-varying dynamics.
problem Model-based policy learning in uncertain, time-varying dynamics.
method Planning regret metric and iterative algorithm for minimizing it.
result Empirical evidence shows the proposed algorithm outperforms existing methods.