Taming "data-hungry" reinforcement learning? Stability in continuous state-action spaces

Summary

The paper presents a novel approach to deriving convergence using two 'stability' properties or assumptions. Improved bounds are derived which show faster convergence than predicted by traditional bounds.

Strengths

1. The authors present a new framework for analyzing RL convergence properties. The authors propose two new stability notions that will help them derive improved convergence rates: a. propogation of estimation errors across iterations b. change of occupancy measure w.r.t policy 2. The paper uses the above two notions (which are relatively mild) to derive bounds in the standard tabular setting that decay as 1/n for offline and log T in the online setting, which is in contrast to previous bounds of 1/n^2 or \sqrt(T) respectively. This takes a step towards partly explaining the fast convergence of RL algorithms observed in practice, atleast in the environments where the stability properties hold. 3. The intuition for the proof of fast rates in section 2.3 greatly helps in clarifying the approach towards deriving these rates. Authors extend the analysis to the setting of linear function approximation. 4. The bounds lead to interesting insights on covariate shifts and are justified as purely being a computing the loss under a different distribution of data. 5. Finally, the authors demonstrate an important benefit of their framework - their bounds do not require any kind of pessimism and yet are able to derive fast bounds. It is discussed under what conditions ignoring pessimism or optimism can still give better bounds.

Weaknesses

1. Validating the theory with some MDPs, even toy domains can greatly help in increasing the quality of paper.

Questions

None

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

4

Limitations

The authors have discusses limitations of their work in Section 4.

Summary

In the context of continual control reinforcement learning, this paper presents a new analysis of how a good Q-function estimate (measured in terms of the Bellman residual norms) induces a good greedy policy (measured in terms of the value gap compared to the optimal policy). The key contribution is the formalization of two "stability" criteria under which the authors prove $O(n^{-1})$ convergence of fitted Q-iteration in the offline RL setting and $O(\log T)$ regret in the online setting, considerably faster than previous results which do not make "stability" assumptions.

Strengths

The paper starts with a very illustrative motivating example that empirically demonstrates the fast $O(n^{-1})$ convergence rate of FQI not explained by the known upper bound of $O(n^{-\frac{1}{2}})$. They go on to introduce two "stability" assumptions about MDPs under which they show that this faster convergence rate is to be expected, and even extend this result to the online setting demonstrating that the previous upper bound on the regret of $O(\sqrt T)$ can be improved to $O(\log T)$ under the same stability assumptions. This is a strong result that will be of interest to the community. To the best of my knowledge, the ideas presented in this paper are novel.

Weaknesses

1. This is the most important point. The two assumptions "Bellman stability" and "Occupation measure stability" are very difficult to understand. There is no proper motivation or illustrative example about when to expect these conditions to hold, and when not to expect so. The authors do translate these conditions to the special case of linear function approximation, but also these "specialized" conditions ("Curv1" and "Curv2") are unintuitive. The paper is very full already and I can understand why the authors decided to save space and not include in-depth discussions of these conditions. However, as these assumptions are really at the core of their results and what differentiates their setting from the "slower rate" setting, I believe the paper would be much clearer if, for example, Section 3 were shortened considerably and instead the stability assumptions were explained in more detail. 2. It is not clear to me what the authors mean by "stability". This term has a concrete meaning in control theory, but I don't understand how this meaning is related to their definitions of "Bellman stability" and "Occupation measure stability". This point is closely related to point 1. 3. (minor) The theorem statements should include the full set of assumptions. For example, Theorem 1 should explicitly say that it holds only under the two stability assumptions. 4. (minor) In Figure 1b, the x-axis uses a logarithm base of $e$, while the y-axis uses the base $10$. This is not just unusual, it also makes the discussion about the slope of $-1$ vs. $-\frac{1}{2}$ confusing, as the plot actually shows a slope of $-\frac{1}{\ln 10}$. 5. (minor) The probability notation in line 307 is confusing. Do you mean $\mu_h^\star(s, a) = \mathbb P_{\xi_1, \pi^\star}[S_h = s, A_h = a]$?

Questions

The analysis presented in the paper shows that fitted Q-iteration converges much faster than previous results show if the environment satisfies certain stability criteria. Is it possible to exploit this stability explicitly in a new method, or is the rate achieved by the general FQI method already optimal?

Rating

7

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors adequately address the limitations of their work.

Summary

This paper demonstrates how sample complexity can be improved under some conditions in offline and online RL. It considers an episodic MDP framework with episodes of length H. One of the contributions of the paper is that, under specific stability conditions for the MDP, getting Bellman residual errors < \epsilon results in a policy (more precisely a policy sequence) whose value sub-optimality is bounded by a quantity proportional to \epsilon^2. As a result, in offline RL, algorithms for which \epsilon is proportional to n^{-1/2} (it is proved for ridge-regression-based Fitted Q-iteration in the paper, under some assumptions) result in a sub-optimality that dwindles proportionally to 1/n, and not n^{-1/2} which is the usual result (n is the number of samples). For online RL, the paper studies a 2-phase algorithm based for on exploration for T0 episodes (similar to the offline case), and a fine-tuning phase based on online RL performing a sequence of rounds (and the number of episodes in round k is twice the number of episodes in round k-1). In this context and with the same assumpions as before, the paper shows that the regret upper bound grows as log(T), T being the total number of episodes. These results identify cases in which the rates of convergence are significantly faster than the usual theoretical results, and intuitions related to these "fast rate cases" are extensively discussed in the paper, and in particular their links with optimism and pessimism. An illustration of fast rate RL achieved in practice is shown on the famous Mountain Car problem.

Strengths

- The paper is well-written, with a high level of technicality. - The results obtained are interesting because they may help shedding light on properties that make RL "easy", and how algorithms could potentially maximize their effectiveness on such easy cases. This is very important because a lot of continuous RL problems are hard mostly because of their high-dimensional and non-linear nature, but the "absorbing regions" of these problems (to re-employ a term used in the paper) often have good smoothness properties and can be categorized as "easy". - The developments of the paper are well motivated, and there are many discussions trying to make a link between the results and simpler intuitions. - Although the detailed analyses are based on assumptions of linear function approximation, the framework proposed in the paper is general, and could be applied to more complex contexts.

Weaknesses

- Discussing thoroughly on the qualitative implications of the results is a strength of the paper, but in some sense it can also be a weakness, since it can be tempting to jump to conclusions that are more global than the restricted context in which results have been proven. For instance, considering all the assumptions on which the results depend, statements like "Thus, the pessimism principle can be useful for problems with smaller sample sizes" must be taken with caution.

Questions

- The global approach has similarities with the much simpler result of logarithmic regret obtained in ["Logarithmic Regret Algorithms for Online Convex Optimization", Hazan et al.]. It raises the following: could some of the results or new results (maybe in a non-episodic framework) be obtained as direct consequences of the result in ["Logarithmic Regret Algorithms for Online Convex Optimization", Hazan et al.]? Typically, x would be a policy, and the update on x would depend on a policy gradient (e.g. with REINFORCE). In this case, would there be any relationship between the assumptions of the paper and the strong convexity required by ["Logarithmic Regret Algorithms for Online Convex Optimization", Hazan et al.]? In a similar direction, analyzing the relationships between the proposed approach and the following papers would be interesting: Lale, S., Azizzadenesheli, K., Hassibi, B., & Anandkumar, A. (2020). Logarithmic regret bound in partially observable linear dynamical systems. Advances in Neural Information Processing Systems, 33, 20876-20888. Agarwal, N., Hazan, E., & Singh, K. (2019). Logarithmic regret for online control. Advances in Neural Information Processing Systems, 32. - Are the required theoretical assumptions valid in the Mountain Car environment? - Typos: line 369 "In the initial T0f episodes" => "In the initial T0 episodes" line 854 "was previously defined (??)"

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

The limitations of the results are well addressed in the paper.