REVIEW 12 cited by
Exploration-Exploitation in Constrained MDPs
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Exploration-Exploitation in Constrained MDPs
read the original abstract
In many sequential decision-making problems, the goal is to optimize a utility function while satisfying a set of constraints on different utilities. This learning problem is formalized through Constrained Markov Decision Processes (CMDPs). In this paper, we investigate the exploration-exploitation dilemma in CMDPs. While learning in an unknown CMDP, an agent should trade-off exploration to discover new information about the MDP, and exploitation of the current knowledge to maximize the reward while satisfying the constraints. While the agent will eventually learn a good or optimal policy, we do not want the agent to violate the constraints too often during the learning process. In this work, we analyze two approaches for learning in CMDPs. The first approach leverages the linear formulation of CMDP to perform optimistic planning at each episode. The second approach leverages the dual formulation (or saddle-point formulation) of CMDP to perform incremental, optimistic updates of the primal and dual variables. We show that both achieves sublinear regret w.r.t.\ the main utility while having a sublinear regret on the constraint violations. That being said, we highlight a crucial difference between the two approaches; the linear programming approach results in stronger guarantees than in the dual formulation based approach.
Forward citations
Cited by 12 Pith papers
-
Toward Optimal Regret in Robust Pricing: Decoupling Corruption and Time
A robust variant of binary search achieves regret O(C + log T) for dynamic pricing with known corruption C and O(C + log² T) when unknown.
-
Decoupling Corruption and Horizon in Robust Contextual Pricing
Robust contextual pricing admits regret O(Cd + d² log T), the first bound that additively separates corruption budget C from horizon T.
-
Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays
Prudent-Banker achieves pseudo-regret Õ(√T + √D) and Õ(1) regret vs. safe comparator in adversarial bandits both with and without delays, matching new lower bounds up to logs.
-
Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses
A new primal-dual algorithm for adversarial linear CMDPs achieves the first sublinear regret and constraint violation bounds of order K to the 3/4 using weighted LogSumExp softmax policies with periodic mixing and reg...
-
Online Resource Allocation With General Constraints
An algorithm for online resource allocation with budget and general constraints achieves O(sqrt(T)) regret in stochastic and alpha-regret in adversarial regimes with bounded constraint violations.
-
Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability
The paper establishes the first tilde O(epsilon^{-1}) upper bounds and matching lower bounds for forward-KL-regularized offline contextual bandits under single-policy concentrability in both tabular and general functi...
-
Learning Safely Without Knowing the World:COMPASS-Hedge
COMPASS-Hedge is claimed to be the first parameter-free full-information anytime algorithm with simultaneous minimax adversarial, gap-dependent stochastic, and near-constant baseline-relative regret.
-
Learning Safely Without Knowing the World:COMPASS-Hedge
COMPASS-Hedge is presented as the first parameter-free full-information anytime algorithm that simultaneously delivers minimax-optimal adversarial regret, instance-optimal stochastic regret, and Õ(1) regret to a basel...
-
Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form
Presents the first algorithm to identify an ε-optimal policy in robust constrained MDPs via epigraph form and bisection search with Õ(ε^{-4}) robust policy evaluations.
-
Fairness in two-player zero-sum games with bandit feedback
A reparametrization reduces fair zero-sum games under bandit feedback to standard games on a transformed matrix, enabling an Õ(T^{2/3}) regret bound for learning general mixed fair equilibria via an Explore-Then-Commi...
-
Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints
A new algorithm achieves Õ(√T) regret and constraint violation in online CMDPs without Slater's condition, plus sublinear α-regret against the unconstrained optimum under adversarial constraints.
-
Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs
PDR-ANPG achieves last-iterate ε-optimality gap and ε constraint violation in CMDPs with sample complexity Õ(ε^{-2} min{ε^{-2}, ε_bias^{-1/3}}) for parameterized policies with transferred compatibility error ε_bias.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.