Regularized Q-learning

Summary

This paper provides Q-learning convergence (asymptotic) in linear architectures with regularization power. Their algorithm is tested on mountain car example.

Strengths

Q-learning convergence in linear architectures is an important problem in RL.

Weaknesses

- The analysis follows ODE style analysis from Borkar and Meyn. So it is asymptotic. However, non-asymptotic guarantees (rate of convergence) can be provided when assuming non-zero stationary distribution (like Assumption 2.1). For e.g. see Chen et al, 22. There are research on extension to QL like TD-Learning convergence in linear architectures. So I think with the current tools one can give such finite time guarantees with some more effort. This work relies on old works such as Gosavi [2006] and Melo et al., [2008]. *Although, I would be curious to know where the current hurdles are.* - A recent work titled "Regularized Q-Learning with Linear Function Approximation" (https://arxiv.org/pdf/2401.15196) are providing non-asymptotic results for a similar problem. I have not looked at the details, but since this appeared in arxiv in Jan 2024, please do include what the contributions are of this work compared to this one. - Section 3.2 can be further improved w.r.t writing. I believe Lemma 3.3, 3.4, 3.5 are provided as independent results to satisfy Eq.(11) (which is crucial for existence and uniqueness of RPBE solution). But I am curious to know why 3 different Lemmas are provided. - How is eq.(15) constructed for $\eta$? I understand Lemma 3.3 helps for (S1). But I am not sure how (S2) came about. - It is mentioned at line 228 that $\eta>2$ is enough for Lemma 3.3. But $\eta<1$ for Lemma 3.4. I really hope Lemma 3.3 and 3.4 are **not required** to be satisfied simultaneously for the current results to hold. - Where is Lemma 3.1 used? We are in linear architecture setting. So Lemma 3.1 (b) inequality which involves $S\times A$ must be avoided. Linear architectures are helpful only when one can replace rate of convergences involving $S\times A$ can be replaced by feature-size $h\ll SA$. My score reflects this review provided here.

Questions

na

Rating

5

Confidence

3

Soundness

1

Presentation

1

Contribution

3

Limitations

na

Summary

This paper introduces a novel approach, RegQ, which is a framework for dealing with linear approximation of Q-function. Compared to the instability of the traditional Q-learning with function approximator, which is known as the deadly triad, RegQ addresses this problem by regularization term, making the algorithm more stable. Also the theoretical approach ensures convergence of linear function approximation.

Strengths

This paper gives a novel approach with theoretical rigor. The most noteworthy strength of this paper is that it tackles a practical problem: the instability of Q-learning with linear function approximator, compared to other theoretical paper that gives impractical solutions. Although the theory is highly technical, this paper gives a good logical explanation, also Figure 1 helps readers to understand the proposed projection operator.

Weaknesses

Most of the concerns arose from the lack of experiment scope, prior work comparison, and implementation. Authors claim about the strengths of the RegQ algorithms, but lots of claims are not confirmed by experiments. Also, the claims are given with the comparison of the prior work, but experimental results are not sufficient to validate those claims. It might be helpful to gain confidence about the novelty of the paper, Also, it is hard to get a precise understanding of the algorithm since there are lack of implementation details.

Questions

In equation (13), what delta_k means? Also, in line 290, why m_k+1 is an i.i.d. noise? Is it an assumption, or can it be proved? In Figure2, the y-axis means the max norm of Q-values. I’m wondering about the value of y axis. At the initial stage of the episode, all of the algorithms have already shown 1e-18, and 1e-20 values, and what the authors claim is RegQ converges when others fail. My question is this: why initial point or other algorithms( which is shown 1e-18 error) is not considered as converged? Also, since values are too small, how could authors prevent the contamination by the floating point error? It will be easy to understand if the authors give more explanation about experiments. In Figure 1c, I can’t find the details about the phases: ‘Blowing up phase’, and ‘Shrinking phase’. I read the author’s error analysis, but there’s no explanation about the phase. Is it just a intuitive naming on the convergence behavior? If not, could you elaborate more about it in the theoretical context?

Rating

4

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Summary

This paper proposes a new Q-learning variant with linear function approximation called RegQ, and proves that its ODE form converges (even when associating it with linear function approximations). Q-learning is famously known to be affected by the 'deadly triad': it tends to diverge in practice when combined to off-policyness, function approximation and bootsrapping. Analyzing formally the convergence of Q-learning combined with simple linear function approximations helps understanding more precisely the mechanisms at play in the deadly triad, and paves the way toward RL with more solid foundations. Authors show empirically that RegQ is faster than two related algorithms with guaranteed convergence. Besides, RegQ relies on a single time-scale, while the other baseline algorithms use two time-scales.

Strengths

- One of the most appealling properties of the framework proposed in this paper is its simplicity: just regularizing projected Bellman equations allows to obtain convergence proofs without relying on several artificial assumptions.

Weaknesses

- In the related work, the paper lists several existing works proving the convergence of Q-learning under linear function approximation with some theoretical assumptions. The assumptions made in the present paper are weaker than most of the ones of existing works, which include restrictions on the Markov chain types, dependency between behavior and target policy, other guarantees than convergence, etc. However, the closest work is by Lee and He (2019), and the present paper does not explicitely state in what way the assumptions are now weaker than in Lee and He. It states that Lee and He's assumption on the behavior and feature matrix seems too stringent to check in practice, but nothing more precise. When Lee and He improved the sufficient condition of Melo et al. (2008), they showed that their new condition was strictly weaker than the previous one, and I believe that a similar analysis should be made. More structure in the comparison would make the paper look less like an incremental modification of Lee and He (2019). - The presented work follows the direction proposed in Lee and He (2019) by reducing the convergence analysis to that of a switching system, establishing simpler upper and lower bound systems and applying the Borkar and Meyn theorem to obtain a proof of the asymptotic convergence. There are of course différences in the approach, but they are in the details. - It can be regretted that the most interesting and novel parts of the paper are in Appendix, which shows that the conference format. might not be the best fit for it.

Questions

- Although there are empirical evaluations, including one on Mountain Car, more ambitious empirical tests with regularized variants of Q-learning-based deep RL algorithms would be interesting. - Could the proposed algorithm fit the framework of regularized MDPs introduced in ["A Theory of Regularized Markov Decision Processes", Geist et al., 2019]? If yes, could results in ["A Theory of Regularized Markov Decision Processes", Geist et al., 2019] be directly applied to the proposed method, including for instance the analysis of the changes on the optimal policy due to regularization (error bound)? Including a discussion on this existing framework in the paper seems relevant. Typos: l9: 'has known to diverge' -> 'was known to diverge' l64: "guarantees convergence" => "guarantee convergence"

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Limitations are well addressed.

Summary

The paper introduces a new regularized Q-learning algorithm "RegQ" suitable for linear function approximation, which essentially adds an $\ell^2$ regularization term to the TD error in semi-gradient Q-learning. The authors prove that this addition ensures convergence of the algorithm and analyze the error with respect to the unregularized solution.

Strengths

The paper centers on an important issue in reinforcement learning: the deadly triad, which is the failure of off-policy TD algorithms when combined with function approximation. This issue has been addressed in practical (deep) RL by expensive methods such as target networks. This paper proposes a simpler solution (specifically for the case of linear function approximation): regularization of the TD error. The paper is very clearly written and provides extensive sections on the background and related work. Their assumptions seem reasonable, and their analysis is rigorous. The overall contribution is highly significant.

Weaknesses

1. The biggest weakness of this paper is the limited experiment section. I understand that this is a theoretical work, and of course don't expect any large-scale experiments. However, the two experiments they do list are not properly explained. (What are these baseline algorithms?) The takeaway from the experiments is that their method has a faster convergence rate, but it is not explained why. The convergence rate is not mentioned elsewhere in the paper, where the focus lies on proving convergence, where other methods do not converge! It would be great to show an environment where RegQ converges while the baseline methods do not, or where the error of RegQ's approximate solution $\theta_\eta^\star$ is smaller than the baselines'. 2. Please comment on Assumption 2.2 (orthogonality of columns of $X$). Could it be relaxed? In high-dimensional ($|\mathcal S||\mathcal A|$) spaces, $h \ll |\mathcal S||\mathcal A|$ _random_ vectors are nearly orthogonal with high probability. Could this be used to show that the result will hold with high probability when using random features? 3. Figure 1c is not properly explained. What are the "shrinking" and "blowing up" phases? Why does the vector $x$, located on the _unit circle_ have norm $0$? 4. For Lemma 3.5, it is assumed that $X^\top D X = aI$. I understand that this is just an example of when a solution to the RPBE exists, but it should be clarified that this assumption is very unrealistic (earlier you wrote that $h \ll |\mathcal S||\mathcal A|$, which is a contradiction). 5. In line 245, you state that, as $\theta^\star = \theta_\eta^\star$ if $\eta = 0$, it holds that $\theta^\star \to \theta_\eta^\star$ if $\eta \to 0$. You are implicitly assuming that $\theta_\eta^\star$ is a continuous function of $\eta$ (at $\eta = 0$), which you should at least mention, if not prove. 6. (minor) In the introduction, you do not mention at all that you also analyze the error $\theta_\eta^\star - \theta^\star$, which to me is a very important part of your work, and would not be out of place in the "summary of main contributions" at the end of your introduction. 7. (minor) As you talk about the deadly triad and how it has been addressed practically in deep RL, you might also want to cite "Deep reinforcement learning and the deadly triad" by van Hasselt et al. (2018). 8. (typo) In line 215, you swap (9) and (4), changing the meaning in a significant way.

Questions

1. Where does equation (6) come from? To solve an equation like $A\theta = b$ iteratively, I would construct a loss function $L(\theta) = \frac{1}{2}||A\theta - b||^2$ and do gradient descent: $\theta_{k+1} = \theta_k - \alpha_k\nabla L(\theta_k)$, where $\nabla L(\theta_k) = A^\top(A\theta - b) + E$, with $E$ containing additional terms if $\nabla A \neq 0$. Equation (6) looks similar at first but is in fact quite different. Could you explain how you arrived at equation (6)? 2. How should equation (15) be interpreted? How "large" does $\eta$ actually have to be to ensure convergence?

Rating

8

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

The authors adequately address the limitations of their work.

Summary

Q-learning is a popular RL algorithm. With function approximation, though, it is known that this algorithm can diverge. This issue is attributed to the `deadly triad': off-policy learning, bootstrapping, and function approximation. This work addresses this issue in the context of linear function approximation. Specifically, this work proposes a novel called Regularized Q-learning, in which a suitable regularization term is added to the standard update rule. The key result (Theorem 5.2) is that this modified algorithm almost surely converges. The proof is based on the switching systems.

Strengths

S1. The paper introduces a new Q-learning algorithm called Regularized Q-learning (RegQ), which ensures convergence under linear function approximation. This addresses the known instability issue in traditional Q-learning with function approximation. S2. The paper uses the switched system theory to derive RegQ's convergence.

Weaknesses

W1. The present work studies **only** the case of Q-learning with linear function approximation under a **fixed behavior policy**. This approach is extremely restrictive and practically not very useful since the quality of the resulting policy critically depends on the choice of the behavior policy. Specifically, as stated by Melo, Meyn, and Ribeiro (2008), for the approximate Q-learning algorithm to discover the optimal policy, the behavior policy would need to be close to the optimal policy itself, which is not feasible. For other choices of behavior policy, the policy estimated by the algorithm could be significantly different from the optimal policy. While Lemma 3.7 provides some guarantees, it is unclear how this result relates the greedy policy, with respect to $X \theta_{\eta}^*,$ to the optimal policy. This is why $\epsilon$-greedy exploration is commonly used in practice. However, the current work does not address this important case. Under $\epsilon$-greedy exploration, several recent studies [1] -- [3] have shown that Q-learning with function approximation suffers from various significant issues beyond instability. Notably, this algorithm can converge to non-locally optimal policies, sometimes even the worst, and exhibit policy oscillation. It remains unclear if the regularization term proposed in the present work would effectively address these issues with $\epsilon$-greedy exploration. References: [1] Patterson, A., Neumann, S., White, M. and White, A., 2023. Empirical design in reinforcement learning. arXiv preprint arXiv:2304.01315. [2] Young, K. and Sutton, R.S., 2020. Understanding the pathologies of approximate policy evaluation when combined with greedification in reinforcement learning. arXiv preprint arXiv:2010.15268. [3] Gopalan, A. and Thoppe, G., 2022. Demystifying Approximate Value-based RL with $\epsilon $-greedy Exploration: A Differential Inclusion View. arXiv preprint arXiv:2205.13617.

Questions

L1. The current work only studies the setting where the $(s_k, a_k, r_{k + 1}, s_{k + 1})_{k \geq 0}$ sequence is sampled in an IID fashion in each iteration. Do you think the results carry over to the scenario with Markovian samples? L2. Are there any realistic examples of the feature matrix $X$ for which the condition in (11) is guaranteed? Minor issues: M1. Line 90: Shouldn't you emphasize what s_0's distribution is? M2. Line 96: Which Markov chain is assumed to be time-homogeneous? M3. Line 176: "... true action value may not lie..." Do you mean the "optimal" value function may not lie in the subspace...? M4. Line 181: `In this case, there are more chances...' Do you have any evidence for this statement?

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

Yes, the authors have discussed the limitations of their work. However, there are more serious issues with the work which I have highlighted.