Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs

Summary

The paper proposes two novel classes of MDPs in the function approximation setting: * Mildly Smooth MDPs: in which the bellman optimality operator outputs smooth functions of degree $\nu$. * Locally Linearizable MDPs: in which there exist a state-action feature mapping into $\mathbb R^d$ and a finite partition of the state-action space that give rise to a Q function approximator class, which is linear in the feature mapping inside each of the partitions (the vector defining the linear mapping is allowed to change between partitions). An online algorithm (CINDERELLA) is presented and a proof of sublinear regret is given for the class of Locally Linearizable MDPs. Subsequently, it is shown that for any Mildly Smooth MDP, there exist a feature mapping and a partition (of size exponential in $d$) that constitute a Locally Linearizable MDP. As a result, a sublinear regret bound of CINDERELLA is derived for the class of Mildly Smooth MDPs: $\tilde O(H \nu_*^d K^{\frac{\nu + 2d}{2\nu + 2d}}$ $ + H^{\frac{2\nu + 2d}{\nu}})$, where $\nu_* := \lceil \nu - 1 \rceil$.

Strengths

* This work proposes a new class of continuous state-action MDPs in which sublinear regret is achievable * In particular, this new class is the currently the most general one that does not suffer from lower bounds exponential in $H$

Weaknesses

* The regret bound has factors that are exponential in $d$, and sublinearity in $K$ is weak (as to be expected in this level of generality). * Similar to other algorithms in this line of work, the CINDERELLA is not computationally efficient and far from being a practical algorithm. * I am not sure what we really learn from such a work; the technical details are complicated even at the level of exposition, and the results are very weak (as to be expected in this level of generality).

Questions

- Definition 1 does not actually contain any structural assumption (for any MDP, one can pick a partitioning and feature maps if we don't require them to satisfy anything), so it doesn't make sense calling such MDPs (that have no structural properties) linearizable. - Line 88 "(iii) we show that all families for which learnable and feasible RL is possible are included in a novel family of Mildly Smooth MDPs defined in this paper": This statement seems way to general - where did you show this? - Does NET-Q-LEARNING indeed obtain regret bound that is independent of $\nu$ for the Strongly Smooth MDP setting? In this case is it strictly better than CINDERELLA for this MDP class?

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

NA

Summary

This paper introduces a notion of local linearization, which is then applied to smooth MDPs. It generalizes the "Eleanor" algorithm into "Cinderella," which, by avoiding a "cardinality of N" term on the suboptimality with respect to the inherent Bellman error, gets sublinear regret for all classes of smooth problems. EDIT: I appreciate the authors' detailed feedback. My score remains unchanged.

Strengths

This paper is written very clearly, exposes all the strengths and weaknesses of its contributions, and makes connections to prior work in a thorough and honest fashion. The paper explain, in particular, why Cinderella is inadequate, and how the parameter learning is decoupled in a way to permit efficient learning. This requires additional technical subtlety in the analysis, but with it comes a bound which would be intractable otherwise.

Weaknesses

This paper is well executed and technically solid, but I believe its main weakness is that the results are not particular surprising to an expert in the area. It seems clear that one can decompose "smooth" MDPs into local linear ones (this has been done, e.g. with zooming bandits and zooming MDPs), and is rather unsurprising that a careful way of handling the analysis makes these objects learnable. I don't seem to see any particular new techniques or insights, and so it is hard for me to be incredibly excited about the result. Still, the paper is executed commendably and for that I lean towards acceptance. There are also some limitations with presentation. Chief among them, the authors should do more to emphasize the algorithmic differences between Eleanor and Cinderalla (as they did so well with Eleanor's limitations for regret). The extent of the discussion seems limited to the sentence "Difference with ELEANOR stays in the fact that parameters relative to different regions are learned separately", which (a) bears elaboration, (b) is somewhat hidden in the mass of text, and (c) is not grammatically correct. I would encourate the authors to explain what techniques and ideas are needed to update the algorithm and analysis for the resultant guarantees.

Questions

What, if any, are the new analysis techniques developed for this setting?

Rating

6

Confidence

4

Soundness

4

Presentation

3

Contribution

2

Limitations

Novelty, somewhat incremental. Moreover, this paper has the computational inefficiency challenges associated with many algorithms in the field, and, like any non-parametric style method, solves exp(dimension, horizon). Lastly, there do not seem to be any lower bounds that characterize the correct exponents.

Summary

The paper introduces the concept of Locally Linearizable MDPs, a class of MDPs that generalizes existing ones like Linear MDPs and MDPs with low inherent Bellman error. In this model, the state-action space is partitioned into $N$ regions, where the Q-functions belong to a class that allows the result of the Bellman optimality operator to be well approximated by a linear function within each region, up to some "Inherent Bellman Error." The authors propose CINDERELLA, a no-regret (computationally inefficient) algorithm designed for this class, achieving regret bound of $Nd\sqrt{K} + \sqrt{d}\mathcal{I}K$, where $N$ is the number of partitions, $d$ is the dimension of the state-action feature space, $K$ is the number of episodes and $\mathcal{I}$ is the Inherent Bellmann Error. Next, they present the class of "Mildly Smooth MDPs". This class is similar yet slightly less general than "Weakly Smooth MDPs," which assume that the output of the Bellman operator on a smooth function remains smooth. Still, Mildly Smooth MDPs are more general than "Strongly Smooth MDPs" and thus positioned somewhere between the two. The authors show that Mildly Smooth MDPs are Locally Linearizable for some partition and Inherent Bellmann Error and by that achieve regret of $H v^d K^{\frac{\nu+2d}{2\nu+2d}} + H^{\frac{2\nu + 2d}{\nu}}$ where $\nu$ is the smoothness parameter of the class.

Strengths

The paper is well-crafted and clearly positions itself within the existing literature. It employs a well-structured pedagogical approach. It first presents a straightforward solution for Locally Linearized MDPs and proceeds to point out that this naive approach's regret bounds are insufficient for deducing a non-trivial regret bound for Mildly Smooth MDPs. This leads to the introduction of their algorithm, which offers improved regret bounds and leads to their main result. The authors conduct a comprehensive analysis of the regret bounds, discussing each component to assess its necessity and provide a comparison with prior work. For the most part, the paper is transparent and addresses its limitations.

Weaknesses

The nature and definition of Mildly Smooth MDPs are not very natural, and it is hard to agree that learning becomes substantially more feasible compared to Weakly smooth MDPs. Specifically, the authors mention that in Weakly Smooth MDPs the regret bound must scale exponentially with $H$, which they consider "statistically unfeasible". However the proposed approach results in a regret bound that scales exponentially with $d$, the dimension of the feature space. This raises similar concerns about the practical feasibility of the setting. The authors claim that for $\nu \to \infty$ the regret becomes of order $\sqrt{K}$, but this is not clearly derived from the provided regret bounds, leaving it unclear whether the result generalizes existing results in Strongly Smooth MDPs.

Questions

* Does [24] also have similar dependency in $d_{v_*}$? If not, I wouldn't consider your regret as *"improved regret bounds for Strongly Smooth MDPs"* * Could you clarify how you achieve $\sqrt{K}$ regret in the limit $\nu \to \infty$?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

For the most part, the paper addresses its limitations.

Summary

The paper discusses the concept of local-linear MDPs which is a general representation class of MDPs that extends previous works on learnable (sublinear regret in $K$) and feasible (polynomial regret in $H$) episodic MDPs.

Strengths

The paper considers important complexity questions associated with the continuous episodic MDP, and is very well-written. Compared to the much more well-studied tabular episodic case, the complexity of continuous episodic MDPs is much more challenging to characterize. The authors identified a class of mildly smooth MDPs and show one can achieve no-regret learning in this regime. The regret bound still has an exponential dependence in $H$ but the authors demonstrated through a continuous bandit special case this exponential dependence is unavoidable. The class of mildly smooth MDPs is larger than the previously studied classes such as kernelized MDPs and strongly smooth MDPs where no-regret learning is possible.

Weaknesses

Even though the theoretical development is sound and complete, I think the authors could do better in further highlighting their contributions which I will use the questions below to elaborate.

Questions

Can you give some concrete examples (can be purely constructed examples or from real-world applications) of mildly smooth MDPs that are not strongly smooth? Since I'm not very familiar with the literature, this could help me further understand what are the additional new problem instances you are able to characterize no-regret learning. Moreover, can you discuss what the current gap between your $\tilde{O}(Hd_{\nu_*}K^{\frac{\nu+2d}{2\nu+2d}}+H^{\frac{2\nu+2d}{\nu}})$ is, especially in terms of $K$?

Rating

7

Confidence

2

Soundness

3

Presentation

4

Contribution

3

Limitations

There is no obvious limitation in this paper.

Summary

This paper studied a structural property called local linearity that makes continuous MDPs learnable. In particular, local linearity means that the continuous state-action space can be partitioned into multiple regions and in each region, the Q-function is linear w.r.t. a unique (different) parameter. The paper first proposed an algorithm to learn MDPs with local linearity and proved that the regret is sublinear. Then, the paper showed that mildly smooth MDPs, where the Bellman operator is smooth, are locally linearizable. So that it demonstrated the broadness of local linearity.

Strengths

1. The studied problem is important. 2. The new concept of local linearity is interesting and indeed capture a broad class of MDPs according the paper.

Weaknesses

1. The proposed algorithm is computationally inefficient. It needs to run over all regions while the number of regions might be exponentially large according to section 4.

Questions

Please see the weaknesses part.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

No further limitations need to be addressed.

Maintaining my score

I thank the authors for their detailed feedback. I still don't feel that the novelty warrants a score increasing, but I do appreciate the authors' clarification.

Reminder to address the author's rebuttal

Dear qoL4, please try to address the author's response and elaborate if it changed your opinion and score. Thank you.

Reply

Thank you for the detailed rebuttal. To be clear, I do not contend the results in the paper did not require technical novelty. In addition, my complaints about the inefficiency and weak guarantees were not to say you could have improved them. My concerns are all with regards to the fact that the problem studied involves many technical details adding a layer of complication over a setting which is already quite niche, one that fundamentally leads to inefficient algorithms and weak guarantees. Hence, I will maintain my score (but certainly do not oppose acceptance).