Regret based Robust Solutions for Uncertain Markov Decision Processes
In this paper, we seek robust policies for uncertain Markov Decision Processes (MDPs). Most robust optimization approaches for these problems have focussed on the computation of maximin policies which maximize the value corresponding to the worst realization of the uncertainty. Recent work has proposed minimax regret as a suitable alternative to the maximin objective for robust optimization. However, existing algorithms for handling minimax regret are restricted to models with uncertainty over rewards only. We provide algorithms that employ sampling to improve across multiple dimensions: (a) Handle uncertainties over both transition and reward models; (b) Dependence of model uncertainties across state, action pairs and decision epochs; (c) Scalability and quality bounds. Finally, to demonstrate the empirical effectiveness of our sampling approaches, we provide comparisons against benchmark algorithms on two domains from literature. We also provide a Sample Average Approximation (SAA) analysis to compute a posteriori error bounds.
This paper makes several good contributions to the 
      literature on robust MDPs. In contrast to previous work, this paper 
      handles both reward and transition uncertainty and also breaks away from 
      making strong assumptions on the underlying uncertainty distributions. 
      One innovation is to sample MDPs from the underlying uncertainty 
      distribution to avoid having to represent the distributions explicitly (as 
      say, a Gaussian reward distribution). They employ MILP to exactly solve 
      for a single deterministic (history-dependent?) policy that minimizes the 
      max regret attainable in a sample of |\xi| MDPs. Or they can approximate a 
      randomized policy for the same problem and the approximation is a bounded 
      distance away from the actual solution [Propositions 2 and 3]. 
      Another innovation is to adapt Cumulative Expected Regret (CER) 
      from the multi-armed bandits literature and apply it specifically for 
      MDPs, which if they also assume independence of uncertainty distributions 
      across states / actions / epoch, then they can scale up to solve uncertain 
      MDP problems with a longish horizon (H = 20) [Proposition 4]. But if one 
      can not assume the independence of uncertainty distributions, then the 
      scale up isn't possible? These contributions are interesting and 
      worthy of publication. I'm slightly unclear on a few things to do 
      with the MDP problem formulation. On line 063, the way that policy is 
      written looks like we're potentially exploring the space of 
      history-dependent policies. But possibly it could mean that it's just 
      dependent on the time horizon we're in. If it's the former, then is 
      'state' not simply the current state, but rather entire rolling histories 
      of state (e.g. state at time 2 = {low in time 0, high in time 1, low in 
      time 2} and not state in time 2= {low in time 2})? And if it is rolling 
      histories of state, what implications does that have for proposition and 
      corollary 1? There's another paper that also takes a 
      sampling-based approach to handling uncertain MDPs from NIPS 2012 called 
      "Tractable Objectives for Robust Policy Optimization". It may be 
      worthwhile to think about how the two papers are related even if that 
      paper isn't looking at a minimax regret objetive. Minor Comments: 
      - Hyphenate 'sampling-based' (e.g. line 050), 'regret-based' (e.g. 
      line 051), state-action' (e.g. line 109). - In a few places, there 
      are parens where it might be cleaner to omit. For example: - (line 
      064) R*(s) (=\max_a R(s,a)) could just be R*(s)=\max_a R(s,a) - 
      (line 098) s (\in S) could just be s \in S - (line 099 s' (\in S) 
      and a (\in A) can be s' \in S and a \in A. - (line 206) \epsilon 
      (= \frac{d^2 - c^2}{r}) can be \epsilon = \frac{d^2 - c^2}{r} - 
      There are some places where I'm not sure the italicizing maximin, reg, 
      creg, SOS2 and br is necessary. Italicize when introducing a term for the 
      first time but not anywhere else (e.g. for maximin). And in an equation, 
      an italicized 'reg' (or 'SOS' or 'br') looks like r*e*g instead of like 
      \text{reg}. - The recursive equations need base-cases: - 
      (p. 2 Definition 1 and 2) - (Supplemental proof of proposition 1) 
      - (p. 2 Preliminaries) you define t and H down on line 099 and 102 
      but you refer to them already in line 061. - (p. 2 Preliminaries) 
      Both the vanilla MDP and uncertain MDP are finite state, finite action, 
      finite horizon problems. But only finite horizon is mentioned on line 096. 
      Point this out by the vanilla MDP problem statement. - (line 087) 
      The '#' comes a bit out of nowhere as it is defined in the supplemental 
      section and even there I'm not sure what it denotes. - (p. 4 
      Equation 5) needs a qualifier that this for all s,a, t, \xi_q? - 
      (p 4, footnote 3) Footnote -> footnote - (line 305) policy will 
      have least regret if it includes *the* CER minimizing policy from t 
      - (line 362) and finally, we refer to the maximin value algorithm 
      as 'Maximin' : if you're looking for stuff to cut to make room, I'd cut 
      this. - (Supplemental 025) *Summing* a geometric progression over 
      the time steps yields - (Supplemental line 134) belong-> 
      belongs - (Supplemental line 134) i = {i_1 … i_H} instead of i = 
      {i_1 … i_{|T|}}?