pipette
ESEspañol

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

Raghav Bongole, Amirreza Zamani, Tobias J. Oechtering, and Mikael Skoglund

Preprint

In the authors' words

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.

Main resultLimitation the authors admit

Appeared: Wednesday, October 21. arXiv. Preprint, not yet peer-reviewed.