In robust Markov decision processes (MDPs), the uncertainty in the transition kernel is addressed by finding a policy that optimizes the worstcase performance over an uncertainty set of MDPs. While much of the literature has focused on discounted MDPs, robust averagereward MDPs remain largely unexplored. In this paper, we focus on robust averagereward MDPs, where the goal is to find a policy that optimizes the worstcase average reward over an uncertainty set. We first take an approach that approximates averagereward MDPs using discounted MDPs. We prove that the robust discounted value function converges to the robust averagereward as the discount factor goes to 1, and moreover when it is large, any optimal policy of the robust discounted MDP is also an optimal policy of the robust averagereward. We further design a robust dynamic programming approach, and theoretically characterize its convergence to the optimum. Then, we investigate robust averagereward MDPs directly without using discounted MDPs as an intermediate step. We derive the robust Bellman equation for robust averagereward MDPs, prove that the optimal policy can be derived from its solution, and further design a robust relative value iteration algorithm that provably finds its solution, or equivalently, the optimal robust policy.
ModelFree Robust AverageReward Reinforcement Learning
Robust Markov decision processes (MDPs) address the challenge of model uncertainty by optimizing the worstcase performance over an uncertainty set of MDPs. In this paper, we focus on the robust averagereward MDPs under the modelfree setting. We first theoretically characterize the structure of solutions to the robust averagereward Bellman equation, which is essential for our later convergence analysis. We then design two modelfree algorithms, robust relative value iteration (RVI) TD and robust RVI Qlearning, and theoretically prove their convergence to the optimal solution. We provide several widely used uncertainty sets as examples, including those def ined by the contamination model, total variation, Chisquared divergence, KullbackLeibler (KL) divergence and Wasserstein distance.
more »
« less
 Award ID(s):
 2229873
 NSFPAR ID:
 10540763
 Editor(s):
 Krause, Andreas; Brunskill, Emma; Cho, Kyunghyun; Engelhardt; Barbara; Sabato, Sivan; Scarlett, Jonathan
 Publisher / Repository:
 Proceedings of Machine Learning Research
 Date Published:
 Volume:
 202
 ISSN:
 26403498
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Robust Markov decision processes (MDPs) compute reliable solutions for dynamic decision problems with partiallyknown transition probabilities. Unfortunately, accounting for uncertainty in the transition probabilities significantly increases the computational complexity of solving robust MDPs, which limits their scalability. This paper describes new, efficient algorithms for solving the common class of robust MDPs with s and sarectangular ambiguity sets defined by weighted L1 norms. We propose partial policy iteration, a new, efficient, flexible, and general policy iteration scheme for robust MDPs. We also propose fast methods for computing the robust Bellman operator in quasilinear time, nearly matching the ordinary Bellman operator's linear complexity. Our experimental results indicate that the proposed methods are many orders of magnitude faster than the stateoftheart approach, which uses linear programming solvers combined with a robust value iteration.more » « less

The Robust Markov Decision Process (RMDP) framework focuses on designing control policies that are robust against the parameter uncertainties due to the mis matches between the simulator model and realworld settings. An RMDP problem is typically formulated as a maxmin problem, where the objective is to find the policy that maximizes the value function for the worst possible model that lies in an uncertainty set around a nominal model. The standard robust dynamic programming approach requires the knowledge of the nominal model for computing the optimal robust policy. In this work, we propose a modelbased reinforcement learning (RL) algorithm for learning an εoptimal robust policy when the nominal model is unknown. We consider three different forms of uncertainty sets, characterized by the total variation distance, chisquare divergence, and KL divergence. For each of these uncertainty sets, we give a precise characterization of the sample complexity of our proposed algorithm. In addition to the sample complexity results, we also present a formal analytical argument on the benefit of using robust policies. Finally, we demonstrate the performance of our algorithm on two benchmark problems.more » « less

The difficulty in specifying rewards for many real world problems has led to an increased focus on learning rewards from human feedback, such as demonstrations. However, there are often many different reward functions that explain the human feedback, leaving agents with uncertainty over what the true reward function is. While most policy optimization approaches handle this uncertainty by optimizing for expected performance, many applications demand riskaverse behavior. We derive a novel policy gradientstyle robust optimization approach, PGBROIL, that optimizes a softrobust objective that balances expected performance and risk. To the best of our knowledge, PGBROIL is the first policy optimization algorithm robust to a distribution of reward hypotheses which can scale to continuous MDPs. Results suggest that PGBROIL can produce a family of behaviors ranging from riskneutral to riskaverse and outperforms stateoftheart imitation learning algorithms when learning from ambiguous demonstrations by hedging against uncertainty, rather than seeking to uniquely identify the demonstrator’s reward function.more » « less

We consider modelfree reinforcement learning for infinitehorizon discounted Markov Decision Processes (MDPs) with a continuous state space and unknown transition kernel, when only a single sample path under an arbitrary policy of the system is available. We consider the Nearest Neighbor QLearning (NNQL) algorithm to learn the optimal Q function using nearest neighbor regression method. As the main contribution, we provide tight finite sample analysis of the convergence rate. In particular, for MDPs with a ddimensional state space and the discounted factor in (0, 1), given an arbitrary sample path with “covering time” L, we establish that the algorithm is guaranteed to output an "accurate estimate of the optimal Qfunction nearly optimal sample complexity.more » « less