TRAPEZE: Minimax-Optimal Episode-Wise Safe Exploration in Tabular CMDPs

We study online learning in finite-horizon tabular constrained Markov decision processes, where every adaptively deployed randomized policy must have conditional expected episode cost at most a prescribed budget. The learner is given a baseline policy with known cost value and safety slack $\kappa >0$. We introduce TRAPEZE, which separates model-based candidate learning from deployment certification. At each model update, scalar optimistic planning over a finite grid of dual multipliers and a deficit-routing rule produce a candidate distribution over policies. While this candidate remains frozen, TRAPEZE directly certifies its cost from subsequent whole-trajectory returns and deploys the largest certified episode-level mixture of the candidate and the baseline. A profile-based Bernstein analysis controls the adaptively selected continuation values without coordinatewise transition confidence. For $K$ episodes, with probability at least $1-\delta$, every deployed policy is feasible and the regret is $\tilde{O}\left(\left(1+\frac{H}{\kappa }\right)\left(\sqrt{SA{H}^{3}K}+SA{H}^2\right)\right)$. We also prove a matching lower bound \Omega \left( \min\left\\{ HK, \left(1+\frac{H}{\kappa}\right)\sqrt{SAH^3K} \right\\} \right) under the same baseline information and episode-wise safety requirement. These results establish minimax optimality up to logarithmic and lower-order terms and show that the inverse safety slack multiplies the full tabular exploration difficulty. Safety concerns conditional expected episode cost, not the cost of every realized trajectory.