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

Q: The regret bound has factors that are exponential in $d$.

Lower bounds show that exponential dependence is $d$ cannot be avoided. If we look at Gaussian bandits with the squared-exponential kernel, a problem family that is strictly contained also in the Strongly Smooth class, [1] ensures an $\exp(d)$ regret lower bound (see Table 1 of [1]). Therefore, exponential scaling in $d$ should not be considered a limitation of our work: it is well-known that RL problems on continuous state-action space can be really hard even for moderately sized $d$.

If, in linear MDP problems, it is well known that $d$ may be very large, almost of the order of $K$, the same thing does not apply here. In fact, the lower bound, even for the simple case $\nu=1,H=1$, entails that $d$ is much smaller than $\log(K)$: $R_K=\Omega(K^{\frac{d+1}{d+2}})\quad \text{and } \quad d\approx c\log(K) \implies R_K=\Omega(K^{\frac{c\log(K)+1}{c\log(K)+2}})=\Omega(K).$ This means that, unless $d\ll \log(K)$, the problem is provably unlearnable.

Q: sublinearity in $K$ is weak

About $K$, we do not only have sub-linearity: of large importance is that for $\nu\to \infty$ one recovers regret of $\sqrt K$ as for tabular or linear MDPs. In fact, having $\nu\rightarrow +\infty$ is very common in physical scenarios: the presence of a Gaussian noise in the transition function is sufficient to guarantee this condition. On the other side "only sublinearity", meant as having a regret order that is slightly less than one, is what competitor works get (See Net-Q-Learning).

Q: I am not sure what we really learn from such a work; the technical details are complicated even at the level of exposition.

The idea of using a feature map that splits across a finite number of regions of the state space is rather intuitive, in our opinion.

Before this work, there were mainly two approaches to continuous MDPs. 1) Discretization-based (e.g. NET-Q_LEARNING) algorithms cannot fully exploit smoothness: the regret scales as $K^{\frac{1+d}{2+d}}$ even for $\nu\gg 1$, which makes them suboptimal. 2) Linearization-based approaches [2], which are able to exploit the parameter $\nu$, achieving regret $\sqrt K$ for $\nu \to \infty$, but fail to give a sub-linear regret bound for $d>2\nu$. The reason can be found in a well-known problem of linear models with misspecification [3].

Q: Definition 1 does not actually contain any structural assumption (...), so it doesn't make sense calling such MDPs (that have no structural properties) linearizable.

As the reviewer correctly states, Definition 1 does not contain any structural assumptions. In fact, as stated in the paper, potentially, every MDP belongs to this class. The point is that the guarantees are "non-trivial" only if the approximation error $\mathcal I$, which is built based on definition 1, is small. Having definition 1 + small $\mathcal I$ corresponds to the intuitive idea of locally linearizable MDP. We will modify the presentation to just define $\mathcal I$ and then call, heuristically, Locally Linearizable MDPs, the ones for which this quantity is small, similarly to what was done in [4].

Our novelty lies in combining the two approaches by splitting the parameters of the feature map (linearization) across different regions (discretization). In this way, we bypass the problem in [1], while having the same benefits of linearization approaches.

This technique partially solves a long-standing open problem in the Kernelized MDP community (see COLT 2024 Open Problem: Order Optimal Regret Bounds for Kernel-Based Reinforcement Learning), as kernelized MDPs are a subclass of our setting.

Q: 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?

As we will clarify in the final version, this sentence does not mean to say "all families that exist" but rather "all families that were defined in the continuous RL literature, to the best of our knowledge". This sentence draws from some results in [2] saying that all the parametric families (LQRs, Linear MDPs, Kernelized MDPs, etc.) with a feasible regret bound are contained in the Strongly Smooth class, which is itself contained in the Mildly Smooth one.

Q: 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?

We remark that, as the lower bound decreases with $\nu$, having a regret guarantee which improves for higher $\nu$ is a desirable feature. Yes, the regret of NET-Q-LEARNING is independent of $\nu$ (for $\nu\ge 1$), but this is a massive drawback w.r.t. our algorithm.

In fact, if one ignores the smoothness of the process, no better regret bound can be obtained than $K^{\frac{d+1}{d+2}}$, the one of NET-Q-LEARNING. But ignoring all the smoothness of the process reveals suboptimal: the higher the $\nu$, the lower the regret. Algorithms like ours, or the ones proposed in [2], as well as the ones coming from the Kernelized RL literature, are able to approach regret order $\sqrt K$ for $\nu \to \infty$, while NET-Q-LEARNING on MDPs cannot do better than $K^{3/4}$ (as $d\ge 2$).

Furthermore, note that many real settings are characterized by a very high value for $\nu$: if the transition of the MDP is affected by a Gaussian noise, $\nu=+\infty$. Ideed, convolution of any function with a Gaussian density becomes infinite times differentiable.

[1] Vakili et al., On Information Gain and Regret Bounds in Gaussian Process Bandits.

[2] Maran et al., No-Regret Reinforcement Learning in Smooth MDPs.

[3] Lattimore et al., Learning with Good Feature Representations in Bandits and in RL with a Generative Model.

[4] Zanette et al., Learning Near Optimal Policies with Low Inherent Bellman Error

Q: 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" ... What, if any, are the new analysis techniques developed for this setting?

We thank the reviewer for giving us the opportunity to clarify this point. Section 3.1 does not explain the novelty of our approach, which is somehow hidden in the appendix; we are going to explain it here and add it to the final version.

Before this work, there were two main approaches to continuous MDPs.

1. Discretization-based (e.g., the Zooming algorithm mentioned by the reviewer) algorithm cannot fully exploit smoothness: due to the "zero-order approximation" the regret scales as $K^{\frac{1+d}{2+d}}$ even for $\nu\gg 1$, which makes them suboptimal.
2. Linearization-based approaches [3], which are able to exploit the parameter $\nu$, achieving regret $\sqrt K$ for $\nu \to \infty$, but fail to give a sub-linear regret bound for $d>2\nu$. The reason can be found in a well-known problem of linear models with misspecification [1].

Our novelty lies in combining the two approaches by splitting the parameters of the feature map (linearization) across different regions (discretization). In this way, we are able to get the best of both worlds: using our local linear approximation, we move from the zeroth-order approximation by Zooming/Net-Q-Learning to an arbitrary order $\nu$, which gives sharper bounds for smooth functions. At the same time, the locality of the feature map bypasses the problem in [1], since it allows us to avoid using tools from linear algebra (like "optimal design" argument) [1,2], which has brought the same regret as [3]. This feature of Cinderella shows that the former techniques can be replaced with the "pigeonhole argument", widely employed in the field of tabular MDPs. As a result, we get the first regret bound for the setting that achieves $\sqrt K$ for $\nu \to \infty$ while being always sub-linear.

In particular, we think that bridging these two approaches - which do not seem to have anything in common - and finding a strategy to elude the lower bound presented in [1] are relevant technical contributions to the learning theory community.

Q: 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).

As the reviewer correctly states, the same computational challenges exists also for celebrated algorithms which work at a similar level of generality. We remark that [4, 5] require access to an optimization oracle over the space of candidate $Q$ functions. This means that if one is interested in approximating a $C^\nu$ function, as in our case, an optimization over a space of $O(2^{(1/\varepsilon)^d})$ functions is needed (if one is satisfied by $\varepsilon-$cover, otherwise $+\infty$).

Q: Lastly, there do not seem to be any lower bounds that characterize the correct exponents.

As we write in Appendix E.7 Lower bounds, matching the lower bound for this setting is a challenging open problem. The best-known lower bound for the order in $K$ is $\frac{\nu+d}{2\nu+d}$, which is inherited from smooth bandits. Nonetheless, even achieving it for Kernelized MDPs with Matern Kernel - a problem which is a subfamily of Strongly Smooth MDPs, which are in turn a subfamily of our setting - is an open problem (see COLT 2024 Open Problem: Order Optimal Regret Bounds for Kernel-Based Reinforcement Learning). Note that, for the former class of processes, a regret order of $\frac{\nu+2d}{2\nu+2d}$ was never proved before this paper; therefore, our result is novel even when restricted to the family of Kernelized MDPs.

[1] Lattimore et al., Learning with Good Feature Representations in Bandits and in RL with a Generative Model

[2] Zanette et al., Learning Near Optimal Policies with Low Inherent Bellman Error

[3] Maran et al., No-Regret Reinforcement Learning in Smooth MDPs

[4] Jin et al. "Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms."

[5] Du et al. "Bilinear classes: A structural framework for provable generalization in rl."

Q: However the proposed approach results in a regret bound that scales exponentially with , the dimension of the feature space. This raises similar concerns about the practical feasibility of the setting. (...) Does [24] also have similar dependency in $d_{\nu_*}$? If not, I wouldn't consider your regret as "improved regret bounds for Strongly Smooth MDPs"

Yes, also [24] enjoys a regret that is exponential in $d$. This can be seen either from the proof of Theorem 11, where the regret scales as $\sqrt{Vol(S\times A)}=2^{d/2}$ or from the fact that the length of their feature map is $\binom{N+d}{N}\approx N^d$ (see last paragraph before section 4.3).
In fact, this exponential dependence cannot be avoided. Indeed, if we look at Gaussian bandits with the squared-exponential kernel, a problem family that is strictly contained also in the Strongly Smooth class, [1] ensures an $\exp(d)$ regret lower bound (see Table 1 of [1]).

Regarding the comparison between our regret bound and the one of [24], we have to remark that not only our regret order is always strictly better, as

$\frac{\nu+3/2d}{2\nu+d}>\frac{\nu+2d}{2\nu+2d}\qquad \forall d,\nu>0,$

but also, and most importantly, our result is always sub-linear, while [24] gets vacuous for $d>2\nu$. Therefore, our improvement over the regret bounds is not limited to avoiding the exponential dependence in $H$.

Q: Could you clarify how you achieve regret $\sqrt K$ in the limit $\nu\to \infty$?

The regret order, for $\nu\to +\infty$, gets $\lim_{\nu\to \infty}\frac{\nu+2d}{2\nu+2d}=1/2.$

In general, this is the condition that papers on continuous space / RKHS seek, as it shows that whenever functions tend to be infinitely smooth the optimal order is recovered.

[1] Vakili et al., On Information Gain and Regret Bounds in Gaussian Process Bandits.

We point out that the regret of our algorithm does not depend exponentially in $H$. Exponential dependence cannot be avoided for the Lipschitz class, and this work is also born to find a class of MDPs that is able to elude this undesirable phenomenon.

Q: 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?

To have an idea of an MDP that is Midly Smooth but not Strongly Smooth, one can think about transition functions of the form

$s'=f(s,a)+U,\qquad U\sim \text{Unif}(b_1,b_2).$

Indeed, the density function of the uniform noise is not continuous, which makes this class of MDPs not Strongly Smooth. Still, we argue that if $f(\cdot,\cdot)$ is not itself discontinuous, this class of MDPs is Mildly smooth. For more details, see the example at the end of page 29 and the whole page 30. Of course, this is true not only for uniform noise, but also for any noise admitting a bounded density function, even discontinuous. We argue that this family of processes is rather realistic and, therefore, the generalization has practical relevance.

Q: Moreover, can you discuss what the current gap between your $\widetilde O(Hd_{\nu_*}K^{\frac{\nu+2d}{2\nu+2d}}+H^{\frac{2\nu+2d}{\nu}})$ is, especially in terms of $K$?

We do not understand which "gap" the reviewer was interested in, so we kindly ask the reviewer to clarify it.

Q: 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.

It is true that the number of regions is exponential in $d$. This makes the computational complexity exponential in this parameter. Still, we argue that this is not a downside w.r.t. the state of the art.

1. State of the art: other algorithms for other very general continuous RL settings require access to an optimization oracle [1, 2] over the space of candidate $Q$ functions. This means that if one is interested in approximating a $C^\nu$ function, as in our case, an optimization over a space of $O(2^{(1/\varepsilon)^d})$ functions is needed (if one is satisfied by $\varepsilon-$cover, otherwise $+\infty$).

2. Magnitude of $d$: if, in linear MDP problems, it is well known that $d$ may be very large, almost of the order of $K$, the same thing does not apply here. In fact, the lower bound, even for the simple case $\nu=1,H=1$, entails that $d$ is much smaller than $\log(K)$: $R_K=\Omega(K^{\frac{d+1}{d+2}})\quad \text{and } \quad d\approx c\log(K) \implies R_K=\Omega(K^{\frac{c\log(K)+1}{c\log(K)+2}})=\Omega(K).$ This means that, unless $d\ll \log(K)$, the problem is provably unlearnable. Therefore, an exponential dependence in $d$ is not as bad as it may seem.

[1] Jin et al. "Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms."

[2] Du et al. "Bilinear classes: A structural framework for provable generalization in rl."