Near-Optimal Sample Complexity for Online Constrained MDPs

Chang Liu, Yunfan Li, Lin F. Yang · 2026

Read Near-Optimal Sample Complexity for Online Constrained MDPs by Chang Liu, Yunfan Li, Lin F. Yang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-15076.txt.

Description

Liu and colleagues study sample complexity for online constrained Markov decision processes, the safety-aware form of reinforcement learning used in driving, robotics, and healthcare. Current methods often break safety rules or demand many samples to reach near-optimal policies. The team treats two settings: relaxed feasibility, where small violations are allowed, and strict feasibility, where none are allowed.

Their model-based primal-dual algorithm balances regret against bounded violations, drawing on online reinforcement learning and constrained optimization. Under relaxed feasibility it returns a near-optimal policy with bounded violation and high probability, using a sample count that matches the lower bound for unconstrained problems. Under strict feasibility it returns a near-optimal policy with zero violation, with sample needs governed by the Slater constant that sizes the feasible region. Learning constrained problems online, they conclude, is no harder than learning unconstrained ones when small violations are allowed.

Catalog record

CREATORChang Liu, Yunfan Li, Lin F. Yang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE105 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-15076

Browse the full library · About the Tower of Babel