Model-based Reinforcement Learning and the Eluder Dimension
We consider the problem of learning to optimize an unknown Markov decision process (MDP). We show that, if the MDP can be parameterized within some known function class, we can obtain regret bounds that scale with the dimensionality, rather than cardinality, of the system. We characterize this dependence explicitly asÕ(
where T is time elapsed, d K is the Kolmogorov dimension and d E is the eluder dimension. These represent the first unified regret bounds for model-based reinforcement learning and provide state of the art guarantees in several important settings. Moreover, we present a simple and computationally e cient algorithm posterior sampling for reinforcement learning (PSRL) that satisfies these bounds.
The paper presents a general theoretical analysis of model-based reinforcement learning algorithms. The presented regret bounds depend on the Eluder dimensions of the function class that we want to learn for the transition function and the reward function. The eluder dimension captures the complexity of the model by, said intuitively, the number of samples that are needed to learn the real function well. This  theoretical analysis is applicable for many model-based RL algorithm, including the commonly used posterior sampling for reinforcement learning (PSRL) algorithm. Quality:The theoretical analysis seems to be well done in the paper, although the proofs are very hard to follow or check. While the theoretical contribution seems to be promising, the presentation of the paper is rather poor and I think it is almost impossible to understand the paper in a reasonable amount of time. For more comments on the clarity of the paper see below. Another maybe not so crucial point is the missing evaluations. I know it is not common for theoretical bounds, but I am always a bit sceptical about these papers where only bounds are presented without any evaluation. You never know how useful the bounds are. I think adding an evaluation of the presented bounds, for example, on a linear quadratic Gaussian (LQG) system  would highly upgrade the paper. For example, the authors could evaluate the regret of the PSRL algorithm for randomly sampled LQG problems with different dimensionalities and show the tightness of the bound. I think such an experiment would also help considerably to understand the contribution and it should be easy enough to do. Significance:Theoretical bounds for a very general set of model-based RL algorithms can have a high impact in the field. However, it is always the question how tight the bounds are in comparison to the results achieved with the real algorithms. Hence, even just a small experimental evaluation of the algorithm on a toy task would considerably increase the significance of the paper. Clarity:-The clarity is the main weakness of the paper. The authors assume too much knowledge of the reader about complex mathematical concepts that are not really common. I think the authors need to concentrate more on transmitting the message of the main result and put more of the very long derivations in the appendix. In the paper it would be more important to explain the intuition and motivation of each step that is important to obtain the bounds.- I think it is necessary to reduce Equation 4 to its most important parts. I do not think that not all the terms are relevant to understand the main message of the paper. The presented bounds go over two full lines. The authors should spend more time on explaining the more relevant parts of the equation (but put the full equation in the appendix)- Explaining the Eluder dimension and the Kolmogorov complexity right in the beginning would greatly simplify the understanding of the paper- define alpha covering and sub-Gaussian noise- define eluder dimension (section 4) before presenting the main results (section 3)- For each of the sections, a small description why the following steps are needed would be really helpful- The paper would also benefit a lot from proofreading. Many sentences are hard to understand due to grammatical mistakes and some of the used words are quite strange (see minor)Originality:The presented analysis using the Eluder dimension is a new contribution. Minor Points:- line 47: falls victim -> reformulate- line 48: exploit MDP structure -> the MDP structure- interedependence -> typo - "what is more, ..." -> reformulate (additionally, moreover, furthermore...)- Define distribution Q for Eq 2 in more detail (distribution over what, is it a conditional?)- 103: "contant"- Corollary 2: Typically in a continuous linear MDP, the action dimension is smaller than the state dimension (half for dynamical systems). How would that change the result?- Conclusion: reformulate "what is more". Quagmire is a quite uncommon word