Worst-Case Bayesian CVaR Regret Bounds for Episodic Markov Decision Processes

Overview & Synopsis

We study the worst-case, over priors, Bayesian conditional value-at-risk (CVaR) of cumulative pseudo-regret in time-homogeneous finite-horizon episodic Markov decision processes. A high-probability guarantee for UCBVI-BF yields a prior-predictive upper bound. A lower bound follows by a three-state MDP and applying a reverse-KL inequality. For a constant number of states, the bounds have the same polynomial dependence on horizon, actions, and episodes, with a logarithmic gap in the risk level.