@inproceedings{
zhao2023provably,
title={Provably Efficient {CV}aR {RL} in Low-rank {MDP}s},
author={Yulai Zhao and Wenhao Zhan and Xiaoyan Hu and Ho-fung Leung and Farzan Farnia and Wen Sun and Jason Lee},
booktitle={NeurIPS 2023 Workshop on Mathematics of Modern Machine Learning},
year={2023},
url={https://openreview.net/forum?id=Vg6oMb7fbh}
}
We study risk-sensitive Reinforcement Learning (RL), where we aim to maximize
the Conditional Value at Risk (CVaR) with a fixed risk tolerance $\tau$. 
Prior theoretical work studying risk-sensitive RL focuses on the tabular Markov Decision Processes (MDPs) setting.  
To extend CVaR RL to settings where state space is large, function approximation must be deployed. 
We study CVaR RL in low-rank MDPs with nonlinear function approximation.  Low-rank MDPs assume the underlying transition kernel admits a low-rank decomposition, but unlike prior linear models, low-rank MDPs do not assume the feature or state-action representation is known. 
We propose a novel Upper Confidence Bound (UCB) bonus-driven algorithm to carefully balance the interplay between exploration, exploitation, and representation learning in CVaR RL. 
We prove that our algorithm achieves a sample complexity of $\tilde{O}\left(\frac{H^7 A^2 d^4}{\tau^2 \epsilon^2}\right)$ rate to yield an $\epsilon$-optimal CVaR, where $H$ is the length of each episode, $A$ is the capacity of action space, and $d$ is the dimension of representations.
Computational-wise, we design a novel discretized Least-Squares Value Iteration (LSVI) algorithm for the CVaR objective as the planning oracle and show that we can find the near-optimal policy in a polynomial running time with a Maximum Likelihood Estimation oracle. 
To our knowledge, this is the first provably efficient CVaR RL algorithm in low-rank MDPs.
Provably Efficient CVaR RL in Low-rank MDPs
Yulai Zhao Wenhao Zhan Xiaoyan Hu Ho-fung Leung Farzan Farnia Wen Sun Jason Lee