Reinforcement Learning in Robust Markov Decision Processes
An important challenge in Markov decision processes is to ensure robustness with respect to unexpected or adversarial system behavior while taking advantage of well-behaving parts of the system. We consider a problem setting where some unknown parts of the state space can have arbitrary transitions while other parts are purely stochastic. We devise an algorithm that is adaptive to potentially adversarial behavior and show that it achieves similar regret bounds as the purely stochastic case.
Additional comments after author feedback: I 
      thank the authors for answering my questions. I now understand how the 
      proposed algorithm works. I do not have any concerns anymore regarding the 
      stochastic check. I see how it may be eventually triggered. 
      ================================================ Original 
      review: The paper describes a new reinforcement learning technique 
      that can handle adversarial scenarios. This is a very important problem 
      that has not been investigated very much. The proposed algorithm is to my 
      knowledge the first that can learn whether each parameter is adversarial 
      or stochastic and infer a robust policy based on that. The paper 
      is generally well written however, some important aspects of the proposed 
      algorithm are not explained. I also have some concerns about the 
      stochastic check. In Figure 3, why is Q the minimum of T-t and a 
      usual backup? If the rewards are always greater than 1, then Q will always 
      be T-t and the algorithm won't be learning anything... I suspect that 
      there is a simple explanation, but I'm not sure... Also, in Figure 
      3, how is \hat{P} estimated? I couldn't find any description of how the 
      transition distributions are estimated. Is it simply the relative 
      frequency counts based on the trajectory observed? I'm also having 
      trouble convincing myself that the stochastic check is reasonable. It says 
      that if the difference between the expected future rewards at (s,a) when 
      computed in two different ways is greater than some threshold, then 
      Pr(s'|s,a) must be adversarial. The threshold is an expression that 
      depends on n and tau, which means that it grows over time. In fact, at 
      some point it will be greater than the difference between Vmax and Vmin 
      where Vmax = T*Rmax and Vmin = T*Rmin. This means that if the agent has 
      not detected an adversarial behaviour by this number of steps, it will 
      never find which parameters are really adversarial. This doesn't seem 
      right. What will happen if the adversary behaves stochastically long 
      enough to ensure that it is not detected and then reveals its adversarial 
      nature after that. Would it manage to inflict arbitrary regret? 
      The empirical evaluation consists of a proof of concept since it 
      includes only a single toy problem that was handcrafted to demonstrate 
      that UCRL2 will fail to converge to a good policy. I encourage the authors 
      to include a more thorough empirical evaluation with several problems, a 
      variation in the degree of adversarial behaviours and to report the 
      running times.