PreprintCC BY 4.0arXiv
Worst-Case Bayesian CVaR Regret Bounds for Episodic Markov Decision Processes
Abstract
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.
Related
- Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling
- Closing the Log Gap: Minimax-Optimal Regret for Episodic RL
- High-Probability Nash Regret for Decentralized Learning in Markov α-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
- Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning
- Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds
BibTeX
@misc{bongole2026worstcase,
title = {{Worst-Case Bayesian CVaR Regret Bounds for Episodic Markov Decision Processes}},
author = {Raghav Bongole and Amirreza Zamani and Tobias J. Oechtering and Mikael Skoglund},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.28157},
eprint = {2610.28157},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.28157},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Worst-Case Bayesian CVaR Regret Bounds for Episodic Markov Decision Processes
AU - Raghav Bongole
AU - Amirreza Zamani
AU - Tobias J. Oechtering
AU - Mikael Skoglund
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.28157
UR - https://arxiv.org/abs/2610.28157
AB - 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.
ER -