Instance-Dependent Regret for CMDPs with Step-Wise Constraints

arXiv:2610.02520v1 Announce Type: cross Abstract: We study online learning in episodic tabular constrained Markov decision processes with step-wise safety constraints. In such a setting, the constraints induce a safe subgraph that shapes the variance of cumulative rewards under feasible policies and, consequently, the difficulty of learning. Exploiting this structure, however, requires learning which actions are safe while controlling constraint violations. We propose Safe Variance-Adaptive Exploration (SVAE), an efficient algorithm that learns candidate safe subgraphs and performs variance-adaptive optimistic planning within them. With high probability, SVAE achieves cumulative regret of order widetilde{O}(sqrt{SAHmin{V_Sigma,KVar^{star}}}+Ssqrt{AH^3min{K,C}}+S^2AH^2) over K episodes, where H is the horizon of a single episode, while S and A are the numbers of states and actions, respectively. Here, Var^{star} is the maximum return variance among safe policies, V_Sigma is the variance accumulated before the first unsafe action is encountered, and C captures the statistical complexity of eliminating actions incorrectly considered potentially safe. SVAE additionally attains widetilde{O}(Hsqrt{SAK}+S^2AH^2) step-wise constraint violation and a gap-dependent violation bound that is polylogarithmic in K. Finally, we establish a lower bound showing that dependence on these instance-specific quantities is unavoidable.

Related

• Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions
• Data- and Variance-dependent Regret Bounds for Online Tabular MDPs
• TraCeS: Learning Per-Timestep Constraint-Violation Credit from Sparse Trajectory-Level Labels

Source: arXiv cs.AI | 2026-10-05