RAAM: The Benefits of Robustness in Approximating Aggregated MDPs in Reinforcement Learning
We describe how to use robust Markov decision processes for value function approximation with state aggregation. The robustness serves to reduce the sensitivity to the approximation error of sub-optimal policies in comparison to classical methods such as fitted value iteration. This results in reducing the bounds on the γ-discounted infinite horizon performance loss by a factor of 1/(1 − γ) while preserving polynomial-time computational complexity. Our experimental results show that using the robust representation can significantly improve the solution quality with minimal additional computational cost.
The paper proposes to use robust MDPs in computing value function approximation for MDPs. The idea is that robustness can compensate for the approximation error when aggregating states.I am generally very positive about the idea. It makes sense and is inline with tying robustness and generalization in other fields of machine learning, esp. classification and regression. A reference to one of the works is probably due.Algorithm 1 is not very well explained. Since the aggregation is given, this can be much simplified (no need for lines 5-9). I think that the role of w and \omega needs to be made much clearer. Perhaps, continuing with Example 3.1 to explain how the robust model is created would do.Section 3.1 is a bit out of the blue. This looks very useful, but can probably be made into a comment.Section 4:The condition that there is a concentration coefficient implies (very) strong mixing. I can't think of many MDPs that would satisfy it (certainly not large MDPs like the ones you'd care about). Theorem 4.1 is a bit strange. I would expect to see \overline{\rho} (\overline{\pi}^*) bounded (i.e., the true optimal policy). But instead you bound \pi^*, the policy where all the actions are forced to be the same in the aggregate. This is what a good aggregation should lead to--what you have now may be trivial if we choose a bad aggregation. So the main issue of finding a good aggregation (as in Bertsekas and Casanton and many other papers) is ignored.After the aggregation we don't have an MDP anymore. This is the case, since the Markovian nature is lost. How is that reflected in the results and proof?I got lost a bit in the proof of Theorem 4.1: I understand why it should work but a better mapping of the proof (overview/steps) would make it much clearer.Theorem 4.4 is the main theorem of the paper, as far as I am concerned. I find the definition of a correlation coefficient interesting, but not very clear. In particular, I don't really understand when $D$ is finite, or even "small." Showing an example where the bound of Theorem 4.4 is computed would be very helpful. RE Section 5: I would have liked to see the aggregation and understand how things play out in terms of the value of the optimal policy (i.e., the true optimal one). At any case, the comparison seems a bit unfair: the (initial) claim is that RAAM can handle the approximation error, not that RAAM is robust to anything. This is a nice bonus. A comparison with the results of Tamar et al from the recent ICML (jmlr.org/proceedings/papers/v32/tamar14.pdf). In particular, a discussion of function approximation for robust MDPs appears there too. I think that the results are sufficiently different, but still, a comparison is due.The references are sloppy. You should double-check them.Update after reading the authors response: Thank you for clarifying. Adding an example with $D$ is small would be good. I like the  paper and the idea.