Demystifying Approximate RL with $\epsilon$-greedy Exploration: A Differential Inclusion View
Authors: Aditya Gopalan
Gugan Thoppe
Venue: Submitted to ICLR 2023 (2023)
Keywords: differential inclusion
epsilon-greedy exploration
function approximation
value-based RL
Q-learning
SARSA
policy oscillation
chattering
discontinuous policies
stability

Abstract: Q-learning and SARSA(0) with $\epsilon$-greedy exploration are leading reinforcement learning methods, and their tabular forms converge to the optimal Q-function under reasonable conditions. However, with function approximation, they exhibit unexpected behaviors, such as i.) policy oscillation and chattering, and ii.) convergence to different attractors (possibly even the worst policy) on different runs, ii.) multiple attractors, and iii.) worst policy convergence, apart from the textbook instability. Accordingly, a theory to explain these phenomena has been a long-standing open problem, even for basic linear function approximation (Sutton, 1999). Our work uses differential inclusion theory to provide the first framework for resolving this problem. We further illustrate via numerical examples how this framework helps explain these algorithms' asymptotic behaviors.

Under review as a conference paper at ICLR 2023
DEMYSTIFYING APPROXIMATE RL WITH E-GREEDY EXPLORATION: A DIFFERENTIAL INCLUSION VIEW
Anonymous authors
Paper under double-blind review
ABSTRACT
Q-learning and SARSA(0) with e-greedy exploration are leading reinforcement learning methods, and their tabular forms converge to the optimal Q-function un- der reasonable conditions. However, with function approximation, these methods exhibit strange behaviors, e.g., policy oscillation and chattering, convergence to different attractors (possibly even the worst policy) on different runs, etc., apart from the usual instability. Accordingly, a theory to explain these phenomena has been a standing open problem, even for basic linear function approximation (Sutton 1999). Our work uses differential inclusion theory to provide the first framework for resolving this problem. We further illustrate via numerical exam- ples how this framework helps explain these algorithms' asymptotic behaviors.
INTRODUCTION
Tabular versions of value-based Reinforcement Learning (RL) algorithms such as Q-learning and SARSA are known to converge to the optimal Q-function under reasonable conditions (Singh et al.) 2000 Jaakkola et al. 1993 Titsikkis 1994). However, the story of their approximate variants (those using function approxdmation) with e-greedy exploration has been inconclusive. On the one hand, these variants, e.g., the Deep Q-Network (DQN) (Mnih et al. 2015), have shown significant empir- ical successes. On the other, there is also growing evidence of undesirable behaviors such as policy oscillation, i.e., indefinitely cycling between multiple policies, or convergence to a sub-optimal or even the worst possible policy [Gordon] 1996 2000, De Farias & Van Roy 2000; Bertsekas [011] Young & Sutton 2020). Accordingly, a mathematical framework to explain such behaviors and, turn, to identify conditions for some minimal reliability has been long-standing open problem, even in the basic linear function approximation case (Sutton 1999 Problem I).
By reliability of an approximate value-based method, we mean some basic notions like i.) stability, ii.) convergence to the optimal policy when the optimal Q-value function lies in the approximating function class, or iii.) convergence
policy with a better Q-value function than the initial pol- icy. Tabular variants of Q-learning and SARSA are reliable in all these three viewpoints under the reasonable conditions that guarantee their convergence (see references above). Likewise, there are sufficient, albeit restrictive conditions (Melo al. 2008 Chen et al., 2019 Carvalho et al.) 2020 Lee & He, 20200 Xu & Gu (020)) under which approximate Q-learning and SARSA with a fixed behavior policy are reliable, at least as per the first notions above. For example, these conditions hold when the behavior policy is close to the optimal policy (the one to be estimated).
In contrast, claim that the reliability of approximate value-based RL methods with e-greedy exploration cannot be taken for granted. To see this, consider Figure [ showing trajectories of different runs of variant of DQN. This variant also employs experience replay and target network as in (Mnih et al. 2015), but uses a linear function instead of a neural network for approximating the optimal Q-value function. The reduction in the approximation power is offset by including the optimal Q-value function in this linear function class") For all the trajectories. the starting conditions are the same and set so that the initial behavior policy close the optimal policy, aligned with the conditions in the fixed behavior policy literature. Thus, one would expect the greedy policy along these trajectories to converge to the optimal policy, Surprisingly, we observe three different behaviors: i.) convergence to sub-optimal policy (red), ii.) oscillation between two sub-optimal policies (blue, tail end) and iii.) convergence to the optimal policy (green).
TTiis ensured by setting one column of the state-action feature matrix to the optimal Q-value function.

---

Under review as a conference paper at ICLR 2023
10a
10P
Greedy policy
722
0
-10
-10
-10 -10P
100
200
400
600
800
1000
0
Iteration (n)
(a)
(b)
Figure 1: Trajectories of three runs DQN on a 2-state 2-action MDP, with a linear 2-dimensional Q-value approximation which perfectly represents the optimal Q Q-value function Q" Figure Ia shows these trajectories the parameter space. The parameters of Q" are denoted by the black star at (1, O). The initial parameter for all trajectories is the same (the black dot) and is chosen that the initial behavior is the e-greedy version of the optimal policy. In this idealized setting, one would have expected all trajectories to go to the star. reality, all of them do converge, but only the green has the desired limit (the initial fading of colors is for of exposition). Figure shows the greedy policies associated with the different trajectories. The limiting greedy policy for the green trajectory unique and is the optimal one; for the red, it sub-optimal policy. In contrast, that of the blue trajectory oscillates between two other sub sub-optimal policies.
The above discussion along with those in (Young & Sutton 2020) show that approximate value- based methods with e-greedy exploration can exhibit several pathological behaviors beyond the textbook instability phenomenon (Sutton & Barto 2018), raising serious doubts about their relia- bility practice. Towards addressing these concerns, a theory to explain the limiting behaviors of approximate value-based RL with greedification is thus extremely important first step.
Existing analyses based on Ordinary Differential Equations (ODEs) are of limited utility in building such theory. To why, note that RL schemes can be viewed update rules of the form
0a+1 0n an (10,) + Mn+1);
220
where h is some driving function, on is the stepsize, and Ma+1 is noise. When is 'nice' overall, e.g., globally Lipschitz continuous, the ODE method is useful to show that the limiting dynamics of (I) is governed by the ODE O(L) h(O())) (Benaim) 1999 Borkar 2009). This is indeed the case in policy evaluation. In value-based RL methods, however, h is quite complex, even with linear function approximation: the update rules involve sampling from distributions which change depending on the iterates. Accordingly. the ODE method has been made to work here only via restrictive assumptions on the sampling distribution, e.g., fixed behavior policy (Carvalho et al.) 2020), near-optimal behavior policy (Melo et al. 2008 Chen et al.) 2019). smooth soft- max behavior policy (Perkins Precup, 2002), Zou et al.] 2019). etc. With e-greedy exploration, the situation worse since, we show, the resultant dynamics also turns out to be discontinuous.
Key Contributions: The main highlights of this work can summarized as follows.
Analysis Framework:
Our work uses Differential Inclusion (DI) theory (Aubin & Cellina 2012) to develop new framework for analyzing value-based RL methods. Our key steps include i.) breaking down the parameter space into regions where the algorithm's 's dynamics are simple, ii.) identifying DI that stitches the local dynamics together, and iii.) using this DI to explain the algorithm's overall (possibly complex) behavior. A DI is a generalization of an ODE which enables this stitching by allowing for multiple update directions at every point.
2

---

Under review as a conference paper at ICLR 2023
2. Explanation of Asymptotic Behaviors: We demonstrate our idea for a variant of lineaf -learning and SARSA(0) with e-greedy exploration. We show that the DIs uncovered by our framework govern the asymptotic behaviors of these algorithms. Our work thus provides the first pathway to systematically explain the whole range of limiting phenomena that approximate value-based RI. methods with greedy exploration can exhibit, and answers the question posed by |Sutton (1999).
The Q-learning and SARSA(0) variants we study do not involve experience replay and the target network in DQN, but instead sample independently from the stationary distribution of the current behavior policy. Our motivation for these variants is threefold: i.) the independent sam- pling serves as idealized replay buffer, ii.) their asymptotic behaviors are amenable to detailed analysis, and iii.) they still show all limiting behaviors of the kind we observe in Figure
3. Illustrations: In Section [] we present case studies that isolate and spotlight the different types of behaviors of the kind shown in Figure[[[unique or multiple attractors, policy oscillations). In each study, we explicitly describe how to identify the appropriate DI using our framework, what the nature of its solutions are, and how they describe the asymptotic behavior of the algorithm. In particular, we explain policy oscillation via a hitherto unseen 'sliding mode' phenomenon.
Several works identify and report variety of complex behaviors for approximate algorithms. These include the classic example of instability for linear Q-learning (Baird 1995) and the phenomenon of chattering in linear SARSA(0) (Gordon 1996) and its approach to bounded region (Gordon 2000). Apart from these, De Farias & Van R (2000) show how approximate value iteration may not possess any fixed points, while [aertsekas| (2011) argues that approximate policy iteration schemes may generally be prone to policy oscillations, chattering, and convergence to poor solutions. More recently, Young & Sutton (2020) and [Schaul et al. (2022) show experimentally how range of approximate value-based RL methods involving greedification exhibit pathological behaviors such as policy oscillation, multiple fixed points, and consistent convergence the 'worst' policy. Our framework helps rigorously explain all these phenomena.
Related Work:
On the theoretical front, while global convergence results exist for Q-learning and SARSA in the tabular setting, their analysis with function approximation presents significant challenges. Even with arguably simple linear function approximation, the general form of the iterations is nonlinear, and there is no natural contraction or Lyapunov function structure that can be exploited. One prominent stream of work focuses on extending linear SA theory to analyze Q-learning with linear function approximation (Melo et al.) 2008 Carvalho al. 2020: Chen et al. 2019) and nonlinear (neural) function approximation (Fan et al. Xu & Gu 2020). However, all these works hold the behav- ior policy fixed, along with imposing other conditions on it (e.g., being close to the optimal policy). These assumptions effectively ensure that the resulting nonlinear SA has a Lyapunov function and thus convergence guarantees. Another such notable work is that [ee & He| (2020), which uses ideas from switched system theory to analyze nonlinear ODEs. This is perhaps similar in spirit to our endeavor as switched systems are also useful for analyzing discontinuous dynamics.
There is also set of analyses that apply SA techniques to study SARSA(0) with incrementally changing policies (Perkins & Precup 2002, Mclo et al. 2008 Zhang et al. 2022 Zou et al. 2019). However, these apply only when the policy improvement operator is Fpschitz-continucn softmax, which ensures the limiting ODE 'very smooth.' Our DI framework is rich enough to handle even discontinuous cases, which is true, e.g., with c-greedy policies.
c.g.,
Finally, we remark that few complicated variants of approximate Q-Jearning have already been an- alyzed using DI based approaches (Maei et al. 2010 [Bhatnagar& & Lakshmanan 2016 Avrachenkov jtt al, 2021). However, the need for using DI there is fundamentally different to the one in ours (the of e-greedy exploration). Maei et al. (2010) and Avrachenkov et al. (2021) look at variants of approximate Q-learning with a fixed behavior policy that represent fiell gradient descent with respect to suitably defined objective functions. A DI arises there due to discontinuities in the sub-gradien of the max of Q-function estimates. In contrast, [Bhatngaar & Lakshmanan (2016) propose a two- timescale variant of approximate Q-learning where the max is replaced by gradient search in the space of smoothly continuous policies. A DI is natural there since the gradient search can lead to one of multiple local equilibria. These differences make their DIs very different to the ones we study; hence, these analyses do not carry over to the case with discontinuous behavior policy changes.
Liinaar Q-learming (resp. lincar SARSA) is Q-learnigg (resp. SARSA) with lincar function approximation. Recall the main purpose for using replay huffers was hreak correlations between samples.
3

---

Under review as a conference paper at ICLR 2023
2 OUR FRAMEWORK AND MAIN RESULT
Take some function f: Rd R2d and consider the generic update rule
0m+1 = On + (0,) + Mn+1],, n 2 0.
The main steps of our framework for analyzing such an update rule are as follows.
1. Partition Rd into regions (R₂) over which f is 'simple': The word simple is subjective and will depend on the algorithm and the tools available for analysis. For approximate value-based RI. methods with e-greedy exploration, Under linear function approximation. f restricted to these regions turns out to be linear and continuous. However, f changes discontinuously when we move from one region the other.
consider regions where the e-greedy policy is constant.
2. Use the Fillippov' idea to stitch the different f-pieces and get a DI: Formally, we combine the different pieces via the set- valued map h R + -2" given by
h((0) n ()((((0))))
(3)
5>0
where Co is the convex closure, and 6) and f(B(0.8) denote the open ball of radius d centered at 6, and its image under f. respectively. An intuitive explanation for h(f) is that it a single update direction {f())} within region of the partition, and the set of all possible update directions in the vicinity of 0 at the boundary between two regions. This construction is standard in control theory to handle discontinuous dynamies (Filippov) 2013) and ensures continuity of h in set-valued sense. The (deterministic) DI that captures the overall dynamics is
(4) Note that, unlike a differential equation, a DI uses E instead of = Further, the RHS now can potentially be a set of several R valued vectors instead of a singleton. A solution of a DI is any map A : [0, 20) + Rd that satisfies (4) However, unlike in ODEs, solutions of a DI need not be unique. fact, this is one of the primary sources for the pathological behaviors in linear Q-learning and SARSA(0) with e-greedy exploration.
0(1) E h((())).
3. Use the DI to explain the limiting dynamics of [ Theorem A.I taken from (Borkar 2009.
Ramaswamy & Bhatnagar] 2017), gives a set of conditions under which (2) asymptotically tracks the solution trajectories of (4). By leveraging this result, the limiting behavior of ( is explained.
We now demonstrate the usage of our framework for explaining the limiting behaviors of linear Q-learning and SARSA(O). We begin by describing our setup and these algorithms' update rules.
Let A(U) be the set of probability measures on a set U. At the heart of RL, we have an MDP (S 7, r)), where S denotes a finite state space, A is finite action space equipped with a total order, is the discount factor, and IP ; S x A + (SS) and r: S x A x S + IR are deterministic functions such that ass.a) = P(s"|s. |s a) specifies the probability of moving from state s to s' under action a, while r(s, a, s') is the one-step reward obtained in this transition. The main goal in RL is to find Q, E R!SI[A,, the optimal Q-value function, associated with this MDP
In practice, however, it is often the case that the state and action spaces are large. In such situations, to reduce the search space dimension, it is common to try and find an approximation to Q., instead of Q. itself. In this work, we focus on linear function approximation. That is, we presume we are given a feature matrix & E ||Si||A(xd and the goal is to find 0₂ E IRd such that Q. s $0_.
Two algorithms to find such 6. are linear Q-learning and SARSA(0) with e-greedy exploration. To enable a joint investigation, we build a unified learning scheme that includes the above two methods as special cases. Let ø" (s, a), where T' implies transpose, denote the (s, a)-th row of Φ. Further, assume that and r satisfy the following condition.
B1. & has full column rank. Further, there exist constants K,,, Ko 2 0 such that [|o(s, a)ll $ K₃ and Ir(s, a, s')) < K, for all s, E S and A.
Next, let (0, 1] and म. S + (AA) the e-greedy policy time 2 0. That is, if 0,, is the estimate of our unified algorithm at time n, then let
1 1-
E(1 1
1/|
if = arg max (8, a d')0n,
(als)
a'
(5)
E/|A/
otherwise.
4

---

Under review as a conference paper at ICLR 2023
We presume that arg max breaks ties between actions that have the same value of (s, a) using the total order on A. Since the state and action spaces are finite, the number of c e-greedy policies is also finite. Suppose these policies satisfy the following condition.
B2. The Markov chains induced by each of the finitely many e-greedy policies are ergodic and, hence, have their own unique stationary distributions.
Finally, let e' E [0. 1]. Then, given some initial estimate 0o E Rd, the update rule of our unified algorithm at time is
0.+1 On + andn an) ón r(sn, an. 8/n) + v0 (s d', o= an)on.
(6)
where on is the stepsize, 8, is the current state at time which we presume is independently sampled from the stationary distribution corresponding to the Markov chair Fl induced by TT On ~ T (+(s),, 0 and e' = corresponds to linear Q-learning and SARSA(0) with e-greedy exploration, respectively. operator for Q-learning is implicitly specified via the manner in which action a' is sampled (from an c'-greddy policy). Note that by independently sampling the state 8, in (6) from xT, 's stationary distribution, we ensure an idealized version of experience replay from the original DQN algorithm.
while s', P(-[sn, ax) and a', ग.. (-1s,,). Clearly, (6) with
particular, the max
Next, suppose that the stepsize sequence (an)n20 satisfies the standard Robbins-Monro condition:
B3. Σn On 0o and Σnzo og < 00.
We are ready to analyze (6). For n 2 0, let Fr == o00, 50, ag, s6.... 8n On-1, -1 d' f(0,) == (s ,,, a,,) [FF),, and M, 1 == ( an) f(O)). Then, it is easy see that (6)
can be rewritten in the form given in (2).
As per Step I in our framework, we partition Rd such that the function f above has a simple form in each region of this partition. For any deterministic policy a = (a(s)) E AA let Pa := {0 e R arg max, o² (s, (s),)) where arg max breaks ties using the total order. Clearly,
Vs E S,)(s) each 0 E Pa. a is the greedy policy corresponding to the Q-value function $8. Alternatively, Pa is the greedy region associated As} partitions IRd, i.e., for any 0 E Rd, there is a unique a such that 0 E Pa.
a. For some a, it is possible that Pa 0. Nonetheless, {Pa a
Let π (resp. TD') be the e-greedy (resp. e'-greedy) policy associated with the policy a. It is easy to see that TH = T and nς = = whenever On E Pa. Next, let dx denote the stationary distribution associated with the Markov chain induced by Tg. Then, when On E Par the expectations of the different terms in d,,(s,) conditional on Fn
ba Eip(sn; an (n)r an s/ = t DGr
and
(8) Here, Di is the diagonal matrix of size |S||A| [A||A] whose (s.a)-th diagonal entry is (a)s), r is the
Aa = E(o(sn (8, an
(Sn, an) 76(8n on) (snn ]] कh DE(D D
vector whose (s,a)-th coordinate is r(s,a)
P(s)s, s'), while P:' is the matrix of size |S||A| x |S]|A] such that Pr ((s, (s' (s', d')) = P(s'|s, a)mr (a'ls'). Note that, when c = c', Aa and ba are exactly the quan- tities that govern the behavior of TD(() with linear function approximation for evaluating the policy T (e.g., (Sutton& & Barto 2018 (9.11))). The f function can now be explicitly written as
1(0) = Σ (ba A.0) 1 E Pa).
REAA
Remark 2.1. Note that f is discontinuous due to the presence of the indicator function 1. However, in each P it is the simple linear function ba AaO; in particular, notice that there is no 'max.'
Assume that the matrices Aa a E AS, satisfy the following condition (cf. Remark 2.5
At any time 2 0, this Markov chain moves from state s' with probability Σ. (s)
5

---

Under review as a conference paper at ICLR 2023
B1. For all A Aa is positive definite, i..., AaA 0.00 E R (Aa need not be symmetric).
The DI from Step 2, i.e., 4 can now be used to understand the asymptotic behavior of (6). In rela- tion to 4 we will say set I' C Rd is invariant if, for every I E I, there is some solution trajectory (E( of (4) with (()) = z that lies entirely in Т. An invariant set I is additionally said to be internally chain transitive if it is compact and, for z, y r, e > 0, and T >> O, there exist m 2 and points To = I, I1, f1,,..... -T-m-1 J. = y in r such that one of the solution trajectories of 4 initiated at z; meets the e-neighhorhood of 24+1 for 0 S i m after time that is equal or larger than T. Such characterizations are useful to restrict the possible sets to which (6) could converge to.
Step 3 of our framework leads to main result.
Theorem 2.2 (Main Theorem: SRI-DI connection). Suppose Bi,..., BB hold. Then, almost surely, the iterates of (6 are stable, iee. sup,, ||0,I| < 00; and converge to a (possibly sample path depen- dent) closed connected internally chain transitive invariant set of the DI in
Proof Outline. The crucial element in the proof is Theorem A. originally proved in (Borkar 2009
Ramaswamy & Bhatnagar| 2017), that discusses the stability and convergence of discontinuous update rules such as and their connections to DIs. The details are in Appendix [A]
Remark 2.3. The almost sure convergence in Theorem 2.2 shows that the limiting DI in captures all possible asymptotic behaviors of our unified scheme given in (6).
Remark 2.4. the only internally chain transitive invariant sets for the DI in (4) are isolated equi- librium points, then (0n) almost surely converges to a (possibly sample path dependent) equilibrium point. In that case, our generic scheme given in [6] will not exhibit parameter chattering.
Remark 2.5. Assumption B. is for ensuring stability, i.e., a.s. boundedness of the sequence (0..) For linear SARSA(0) with e-greedy exploration, B follows follow Gordon 2000). For Q-learning, B. need not hold in general. In that case, Theorem 2.2 claim holds a.s. on the event where the iterates are stable: {supa20 ||0,.|| < oo}; see the first extension in Section 2.2. of (Borkar 2009).
ILLUSTRATION VIA NUMERICAL EXAMPLES
We illustrate here how Theorem 2.2 can be used to explain the limiting dynamics of linear Q-learning and SARSA(0) algorithms with e-greedy exploration. Specifically, we consider a range of 2-state 2-action MDPs, whose rewards, probability transition matrices and state-action features have been generated via random search (each MDP's details, such as probability transition function, reward function, discount factor, and the algorithm's exploration parameter c, are provided in the Appendix). In each case, the MDP and features induce 2 greedy policies, for simplicity. Even in these 'simple' settings, we see that the algorithms' trajectories exhibit complex and non-trivial phenomena. We then explain their causes via analysis of the associated DIs.
A. Two self-consistent greedy regions Multiple attractors. The parameter space I² is parti- tioned into 2 greedy regions (see definition of Pa in Section Pa. and Pa, via greedy policies and a2, respectively.
Let us call the point A, a landmark for the partition Pa,, i = 1,2, where the Aa and ba are as in 7 (all matrices our examples will be positive-definit, hence invertible). The landmark Am.b,. the (unique) point to which the ODE 0(t) = ba, Aa,0 0 would converge. Put another way, is the point to which the Q-learning algorithm would converge were it to always sample actions on in (6) according to the e-greedy policy based on a,
The greedy regions in this example are both self-consistent. By this, we mean that each contains its own landmark: Ar, E Pa, for i = 1, The landmarks, along with their respective color-shaded greedy regions, shown as diamonds in Fig. 2a Note that since each greedy region must be cone and there are only 2 regions, each must be a halfspace with the origin 0 on its boundary.
Fig. 2a shows two sample paths of the iterates 0, of Q-learning (update (6) and é' = 0), with c O.I greedy exploration, = 0.75 discount factor, decaying stepsizes an = @(1/n) and an iteration count of 20, 000, against the backdrop of the partition diagram. The starting positions, marked with black dots, were chosen arbitrarily. Note that segments of a trajectory are often parallel to each other, because the number of directions to move from iterate is finite in finite MDP

---

Under review as a conference paper at ICLR 2023
6
2-
-8
-4
-10
-4
-6 -2 2 4
8h
81
(a)
(b)
(c)
Figure 2: Trajectories under Q-learning. (Left) An MDP where function approximation in IR? gives rise to greedy regions, both of which self-consistent. The shaded represent the greedy regions, with the (self- consistent) landmarks for cach partition' 's dynamics marked with diamonds of the respective colors. Two sample trajectories of Q-learning, with ((1/m) /n) stepsize schedule, overlaid the partition diagram with their starting iterates marked with black dots. The trajectories converge (behavior). The differential inclusion here has only the self-consistent landmarks as asymptotically stable attractors (cause). (Center) An MDP where function approximation in R gives rise to greedy regions, neither which self-consistent. Two sample trajectories schedule, overlaid on the partition diagram with their starting iterates marked with black dots. The iterates converge to a unique point on the partition boundary (bchavior) The differential inclusion here has a single 'sliding mode' attractor the boundary (cause). (Right) An MDP where function approximation in R² gives rise to 2 greedy regions, exactly one of which which self-consistent. Two sample trajectories of the iterates of Q-learning, with (1/n)) stepsize schedule, marked with black dots. The iterates always converge to the unique self-consistent point one of the partitions (behavior). The differential inclusion here has unique attractor (cause).
one of the self-consistent landmarks
iterates of Q-learning, with a (1/mx) stepsize
overlaid on the partition diagram with their starting iterates
20
10
10
0
110
-10
-20
-20
33
-30
40
40
550
500
550
-30 -20 10
-60
50
40
-30
10
9:
6,
Figure 3: Sample trajectories of the iterates of Q-learning and SARSA(0), with ((1nn) stepsize schedule, overlaid on their greedy regions. (Left) In the landmark structure induced by Q-learning, there is no 'sliding mode' point on the boundary of the green and red partitions, thus the trajectories move towards the red land- mark in this case. (Right) the landmark structure induced by SARSA(0), there is 'sliding mode' equilibrium point the boundary of the green and red regions towards which both trajectories move (see inset).
Though the trajectories may traverse both greedy regions, they eventually approach one the two landmarks (this observation remains true after several repeated trials). How can this be explained via our theoretical framework?
To answer this, let look at the DI 0(t) h(O(t)) induced by Q-learning for this MDP, obtained via (9). Specifically, h0) equals the singleton set (b., Aa, 0} for 9 lying in the interior of the blue region (say Pa,) the singleton set {b,g Ang0} in the interior of the red region (say Pa,)) ) and the

---

Under review as a conference paper at ICLR 2023
connected segment (fba) Aa, 8, bas - A)) whenever A is on the (I-dimensional) boundary of the two regions. In this DI, each point in the interior of greedy region suffers a drift 'towards' the region's 's landmark. Points on the boundary, however, can be subjected to any drift in the convex hull of the drifts induced by each partition's is affine dynamics at that point.
Theorem 2.2 says that with probability 1, the iterates must converge to invariant and internally chain transitive set of the DI. Recall that an invariant set / means that 4o E I there is some trajectory 0(1), -x < L < 00 lying entirely in and passing through 0 at time O. Roughly, for I to be internally chain transitive, for any pair of points Ostan: 0end 7, closeness tolerance 7) and travel time T, we must be able to find a solution of the DI and intermediate waypoints in I such that the solution starts close to Sstart ends close to end and reaches close each successive waypoint after time T'
Examining this DI leads to the conclusion that it possesses only 3 invariant, internally chain transitive singleton sets the 2 limiting dynamics points, plus point 6 on the boundary whose convex hull contains the 0 vectof - for the following reasons. These 3 singletons are certainly invariant and internally chain transitive sets, because for each there is a solution of the DI that always stays at that point for all -00 < L < 0o by virtue of zero drift. It also follows that there can be no other invariant set for the DI, because (a) any solution of the DI that, at any time, is in the interior of region continues within that region towards its respective landmark, and (b) any solution that, at any time, is the boundary but not at 8 must suffer a drift that eventually pushes it into some greedy region's 's interior or along the boundary to 8º. We do not give a formal proof that these are the only invariant, internally chain transitive sets of the DI; the reader is directed to standard references on DIs Aubin & Cellinal (2012) Thus, according our result, the stochastic iterates of Q-learning must eventually approach one of these 3 isolated points. We additionally remark that the point 1 on the boundary is an unstable cquilibrium point, because any neighborhood around it contains points (in the interiors of Pa. and Pay) from where the DI's solutions will escape towards the landmarks. If the martingale difference noise (M,) is sufficiently 'rich', i.e., it does not put all its probability mass in a subspace of IR?, then random chance will cause the iterates to eventually escape this unstable equilibrium point. This condition will hold if all state-actions' features span R², which they indeed do.
Our analysis also brings out the fact that asymptotically (as -> oo), there are no policy oscillations (iterates jumping regions infinitely often) nor parameter oscillations (iterates that 'bounce between' two regions at positive distance) that can occur, because the iterates must eventually stabilize around one of the two landmarks in the interior of the greedy regions.
B. No self-consistent greedy regions - Sliding mode attractor. We consider an MDP and feature set that induce 2 greedy regions, each of which has its landmark in the other region. Trajectories of Q-learning with the same parameters and stepsizes as before. appear to move eventually towards the boundary between the two regions (Fig. 2b).
Reasoning about the DI in this case, and its solutions, paints a qualitatively different picture than that of the previous example. As before, for each point @ in the interior of any greedy region, there is a singleton, nonzero drift h(0)- = (b- based on the b, A of the region containing 0. However, this drift is directed toward the other region. It follows that any trajectory of the DI initialized at a region's 's interior point 0 will reach the boundary in finite time, which rules out interior points from belonging to any internally chain transitive sets.
The only possible invariant, internally chain transitive sets, then, are to be found on the 1- dimensional boundary between the 2 regions. A moment's thought convinces us that the only such set is the singleton comprising the unique point 6* on the boundary for which both dynamics' drifts point in opposite directions (equivalently, 0 is in their convex hull). This point is strikingly different than the point 0 of the previous example in that is a globally stable equilibrium point- - indeed, any deviation from this point pushes the DI's trajectory towards it rather than away from it. More- over, observe that any trajectory of the DI started from an interior point of a region first reaches the boundary in finite time, due to a positive 'velocity' towards the boundary. Thereafter, it "slides'
'The coordinates of this (2 22dimensional) point can be analytically obtained by solving 2 equations express-
ing that: (1) 8 lies on the boundary of the greedy regions, (2) the vectors bans Aan H" and Danue A Auu H point in opposite directions.
8

---

Under review as a conference paper at ICLR 2023
along the boundary to reach 0*, i..., 8(t) always belongs to the boundary Vt 2 to for some time tu- Such a trajectory is termed a sliding mode and has been extensively studied in control theory (see
e.g., Utkin (201))).
To our knowledge, the existence of sliding modes and associated equilibria has not been previously demonstrated for approximate RL. algorithms. Also, our main result (Theorem 2.2 guarantees that asymptotically, the stochastic iterates 6, will not oscillate or chatter, although policy oscillations are possible (the iterates may cross the boundary infinitely often on their way to (*))
C. Only one self-consistent greedy region - Unique landmark attractor. We consider an MDP that, with linear Q-function approximation in RR2,, induces two greedy regions with exactly one of them being self-consistent (Fig. [c) The DI for this setting has the property that points in the red region will experience a (vector) drift, towards the boundary, which is bounded away from in norm. As result, any DI trajectory that starts in the red region will, in finite time, hit the boundary. The driving (set-valued) function h(0) for each boundary point can be shown to have all its constituent drift vectors 'pointing into' the blue region, so any solution from the boundary must instantaneously leave it. Continuing from here, the trajectory moves towards the blue landmark, which can be shown to be the sole invariant, internally chain transitive set of the DI. It is thus clear, from Theorem 2.2 that all the original stochastic iterates of the algorithm must eventually approach this point. This is a situation in which no policy parameter chattering occurs. Also, as observed by Young and Sutton Young & Sutton 2020), is possible that this (single) landmark point to which every trajectory converges may represent very poor quality approximation for the optimal value function.
Figs. 3a and [36] show that even with the same MDP and features (and hence greedy regions), Q- Learning and SARSA(O) can induce different landmark structures, resulting in different trajectory behavior. We discuss other examples such as the chattering phenomenon observed in Gordon [196);;
Young & Sutton 2020) in the Appendix.
CONCLUSION AND FUTURE DIRECTIONS
We introduced the novel toolset of SRIs and DIs to help understand the algorithmic dynamics of approximate RL algorithms. We may have merely scratched the surface with regard to wielding the DI approach to its fullest potential. Our framework paves the way for more comprehensive understanding of existing approximate-RI algorithms as well as the design of new schemes with 'well-behaved' DIs, hopefully resulting in value beyond just analysis to the realm of synthesis.
On a somber note, the insights we have uncovered about algorithms using arguably the simplest possible (linear) function approximation casts doubt on their utility in more complicated, nonlinear is plausible that there are many more failure modes these set-
approximation architectures. tings than the range observed in the linear case, also seen by Young & Sutton (2020) in neural approximation. Even with linear function approximation, we have shown in this paper that (a) one could converge multiple attractors with disparate qualities, (b) one could oscillate between mul- tiple policies' greedy regions, making it difficult to devise simple stopping criteria (c) even if one converges always
unique point within greedy partition, the induced greedy policy could be arbitrarily bad - these spell doom for the practitioner unless carefully addressed and investigated. Separately, we acknowledge that our theory addresses only linear function approximation and more work is needed to extend it to nonlinear approximation architectures.
Yet another promising direction for future research, which is not taken up in this paper, is that of the quality of the limiting iterates (assuming there is some reasonable form of convergence). Again, Young & Sutton (000 'Worst-case example') and [Bertsekas] (201T) point out that approximate policy iteration schemes could very well converge to the "worst possible outcome', which, perhaps, with suitable design considerations based on the DI connection, can be avoided new algorithms to come. For instance, a whole new class of algorithms can arise by assigning arbitrary values of e, in the generic update (6) with favourable properties. On a slightly different but related note, our work also reinforces the fact that merely ensuring stability of incremental RL algorithm's 's iterates is by no means sufficient to guarantee good performance discontinuous policy updates often swamp out gains from stability by inducing complex and varied convergence modes.

---

Under review as a conference paper at ICLR 2023
REFERENCES
J-P Aubin and Arrigo Cellina. Differential inclusions: set-valued maps and viability theory, volume 264. Springer Science Business Media, 2012.
Konstantin E Avrachenkov, Vivek Borkar, Hars Dolhare, and Kishor Patil. Full gradient dqn re- inforcement learning: provably convergent scheme. In Modern Trends in Controlled Stochastic Processes: pp. 192-220. Springer, 2021.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pp. 30-37. Elsevier, 1995.
Michel Benaïm. Dynamics of stochastic approximation algorithms. In Seminaire de probabilites XXXIII, pp. 1-68. Springer, 1999.
Michel Benaim, Josef Hofbauer, and Sylvain Sorin. Stochastic approximations and differential inclusions. SIAM Journal on Control and Optimization, 14(1))328-344) 2005.
Michel Benaïm, Josef Hofbauer, and Sylvain Sorin. Stochastic approximations and differential inclusions, part ii: Applications. Mathematics of Operations Research, 31(4):673 -69,,,677366,,, 2006.
Albert Benveniste, Michel Métivier, and Pierre Priouret. Adaptive algorithms and stochastic ap- proximations, volume 22. Springer Science & Business Media, 2012.
Dimitri P Bertsekas. Approximate policy iteration: A survey and some new methods. Journal of Control Theory and Applications, 903):300-335, 2011.
Dimitri P Bertsekas and John N Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996.
Shalabh Bhatnagar and K Mohan Babu. New algorithms of the Q-learning type. Automaticu, 44(4): 1111-1119, 2008
Shalabh Bhatnagar and K Lakshmanan. Multiscale q-learning with linear function approximation. Discrete Event Dynamic Systems, 26(3):477-50,, 2016.
Vivek S Borkar. Stochastic approximation: a dynamical systems viewpoint, volume 48. Springer, 2009.
Diogo Carvalho, Francisco S Melo, and Pedro Santos. new convergent variant of l-larnning with linear function approximation. Advances in Neural Information Processing Systems, 33:19412- 19421, 2020.
Zaiwei Chen, Sheng Zhang, Thinh T Doan, John-Paul Clarke, and Siva Theja Maguluri. Finite- sample analysis of nonlinear stochastic approximation with applications in reinforcement learn- ing. arXiv preprint 1rXiv:1905.11425. 2019.
Jorge Cortes. 2008
Discontinuous dynamical systems. IEEE Control systems magazine, 28(3):36-73
Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor. Finite sample analyses for td (0) with function approximation. Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
Daniela Pueci De Farias and Benjamin Van Roy. On the existence of fixed points for approximate value iteration and temporal-differeee learning. Journal of Optimization theory and Applica- tions, 105(3):589 608, 2000.
Jianqing Fan, Zhaoran Wang, Yuchen Xic, and Zhuoran Yang. theoretical analysis of deep q- learning. In Learning for Dynamics and Control, pp. 486 489. PMLR, 2020.
Aleksei Fedorovich Filippov. Differential equations with discontinuous righthand sides: control systems, volume 18. Springer Science & Business Media, 2013.
Geoffrey J Gordon. Chattering in sarsa (lambda)-a emu learning lab internal report. 1996.
10

---

Under review as a conference paper at ICLR 2023
Geoffrey J Gordon.
Reinforcement learning with function approximation converges region. Advances in neural information processing systems, 13, 2000.
Tommi Jaakkola, Michael Jordan, and Satinder Singh. Convergence of stochastic iterative dynamic programming algorithms. Advances in neural information processing systems, 1993.
Lasota and Aaron Strauss. Asymptotic behavior for differential equations which cannot be locally linearized. Journal of Differential Equations, 10(1):152-172, 1971.
Donghwan Lee and Niao He. A unified switching system perspective and convergence analysis of q-learning algorithms. Advances in Neural Information Processing Systems, 33, 2020.
Bo Liu, Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, and Marek Petrik. Finite-sample analysis of proximal gradient td algorithmss In UAI, pp. 504-513. Citeseer, 2015.
Hamid Reza Maei, Csaba Szepesvári, Shalabh Bhatnagar, and Richard S Sutton. Toward off-policy learning control with function approximation. In /CML, 2010.
Peter Marbach and John N Tsitsiklis. Simulation-based optimization of markov reward processes. IEEE Transactions Automatic Control, 46(2):191-209 2001.
Francisco S Melo, Sean Meyn, and M Isabel Ribeiro. An analysis of reinforcement learning with function approximation. In Proceedings of the 25th international conference on Machine learning, pp. 664-671, 2008.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51 (58854)):529-538 2015.
Alexander P Molchanov and Ye Pyatnitskiy. Criteria of asymptotic stability of differential and difference inclusions encountered in control theory. Systems & Control Letters, 13(1):59-64 1989.
Theodore Perkins and Doina Precup. A convergent form of approximate policy iteration. Advances in neural information processing systems, 15, 2002.
Theodore Perkins and Mark D Pendrith. On the existence of fixed points for q-learning and sarsa in partially observable domains. In ICML, pp. 490-497, 2002.
Arunselvan Ramaswamy and Shalabh Bhatnagar. A generalization of the borkar theorem for stochastic recursive inclusions. Mathematics of Operations Research, 42(3):648-66) 2017.
Gavin Rummery and Mahesan Niranjan. On-line Q-learning using connectionist systems, vol- ume 37, Citeseer, 1994.
Tom Schaul, André Barreto, John Quan, and Georg Ostrovski. The phenomenon of policy churn. arXiv preprint arXiv:2206.0073: 2022.
Satinder Singh, Tommi Jaakkola, Michael I. Littman, and Csaba Szepesvári. Convergence results for single-step on-policy reinforcement-leamiig algorithms. Machine learning, 38(3):287-308, 2000.
Georgi V Smirnov. Introduction to the theory of differential inclusions, volume 41. American
Mathematical Society, 2022.
Richard Sutton. Open theoretical questions in reinforcement learning. In European Conference on Computational Learning Theory, pp. 11-17. Springer, 1999.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, Csaba Szepesvári, and Hamid Reza Maci. A convergent (n) temporal-diiferenee algorithm for off-policy learning with linear function approximation. In NIPS, 2008.
John N Tsitsiklis. Asynchronous stochastic approximation and q- q-learning. Machine learning, 16
(3):155-202, 1994.
11

---

Under review as a conference paper at ICLR 2023
John N Tsitsiklis and Benjamin Van Roy. An analysis of temporal-difference learning with function approximation. IEEE transactions on automatic control, 42(5):674-69)) 690, 1997.
Vadim Utkin. Sliding modes in control and optimization. Springer Science & Business Media, 2013.
Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. 1989.
Pan Xu and Quanquan Gu. A finite-time analysis of q-learning with neural network function ap- proximation. In International Conference Machine Learning, pp. 10555-10565. PMLR, 2020.
Vinayaka G Yaji and Shalabh Bhatnagar. Stochastic recursive inclusions with non-additive iterate- dependent markov noise. Stochasticx, 90(3):330-363, 2018.
Kenny Young and Richard Sutton. Understanding the pathologies of approximate policy evaluation when combined with greedification in reinforcement learning. arXiv preprint arXiv:2010. 15268 2020.
Shangtong Zhang, Remi Tachet, and Romain Laroche. On the chattering of sarsa with linear function approximation. arXiv preprint arXiv:2202.06825, 2022.
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for sarsa with linear function approximation. Advances in Neural Information Processing Systems, 32, 2019.
12


Reviews:
[{"review_id": "iyxaEsBL-I", "reviewer": "Reviewer_ieqE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes to apply theory of differential inclusion to understand and explain the behavior of epsilon-greedy based value-learning algorithms with function approximation, such as Q-learning and SARSA(0) with epsilon-greedy exploration. The main result (Thm 2.1) characterizes the asymptotic behavior of aforementioned algorithms under a few assumptions.", "summary_of_the_review": "=== **Background question** ===\n\nI would like to clarify a few sentences in the intro section of the paper. The authors write\n\n\"The expected behavior here would be convergence to the optimal policy...\"\n\nIs the behavior expected because the representation matrix Phi contains the optimal Q-function as one of its columns, so that we should expect the linear function approximation to be able to learn the optimal Q-function and therefore optimal policy. In other words, the \"expected\" here is purely based on realizability of the target Q-function in the function class.\n\nIn practice, such convergence behavior is not observed. I wonder intuitively if this can be explained by the fact that though the optimal Q-function can be represented within the class of linear functions, the algorithm itself can take a path that does not lead to the optimal Q-function. This reminds me of certain conclusions in the policy gradient case, where if the function class is not closed under the policy improvement operator, there is no guarantee to convergence even though optimal Q-function is representable. Can the authors comment on the potential connection here? For general audience, it would also be interesting to understand more of the intuitions of the jittering / non-convergence behavior.\n\n[1] Bhandari et al, 2019, Global Optimality Guarantees For Policy Gradient Methods\n\n=== **Textbook instability** ===\n\nI am a bit confused by the use of \"textbook instability\". What does this instability refer to exactly?\n\n=== **$h$ not Lipschitz continuous***\n\nI find the background under Eqn 1 a bit confusing in wording. If I understand correctly, $h$ is Lipschitz continuous when doing policy evaluation, as the system is linear; when doing control with $\\epsilon>0$-greedy, $h$ is generally not Lipschitz continuous. Is this the case? Maybe worth clarifying more here.\n\n=== **Main result** ===\n\nAssumption B4 I think need further explaining. From the background under Eqn 3, $\\epsilon>0,\\epsilon'=0$ corresponds to Q-learning; $\\epsilon'=\\epsilon>0$ corresponds to SARSA(0). The $A_a$ matrix is\n$$\\Phi^T D_a^\\epsilon (I-\\gamma P_a^{\\epsilon'}) \\Phi$$\nI think it is true that when $\\epsilon'=\\epsilon$, the above matrix is PD i.e., $x^T A_a x>0$ for any vector $x$, because essentially $D_a^\\epsilon$ and $P_a^{\\epsilon'}$ are diagonal matrix and one-step transition matrix of the same $\\epsilon$-greedy policy. \n\nHowever, it is not immediately clear to me why in the Q-learning case $\\epsilon'=0,\\epsilon>0$ the $A_a$ matrix is also PD. If B4 is assumed true, it seems to be a very big assumption? I wonder having assumption B4 in place would be in conflict with much of the prior literature in analyzing Q-learning with FA, where it seems that obtaining theoretically justified convergence would need to impose stringent assumption on the data process, such as near on-policy [1].\n\n[1] Melo et al, 2008, An Analysis of Reinforcement Learning with Function Approximation\n\n=== **Presentation** ===\n\nPresentation-wise, I'd certainly appreciate more comprehensive background introduction on DI. The whole paper is pretty dense, especially in Sec 2, where it seems tricky for general audience to understand the main technical points of the paper unless equipped with sufficient background in DI. \n", "strength_and_weaknesses": "=== Strength ===\n\nThe paper seems to provide a very interesting toolkit to systematically understand the behavior of value-based learning algorithm under linear FA and with epsilon-greedy exploration, which is a useful abstraction for many commonly implemented RL algorithms. This might pave the way for future investigations into similar topics.\n\n=== Weakness ===\n\nA potential weakness of the paper is that it is not clear what are the implications of the results in the paper and how significant they are. The main theoretical statement Thm 2.1 claims that under certain conditions, parameter iterates of such value-based algos can jitter within a set of solutions. There is little characterization of how the set of solutions relate to each other (e.g., quality of the solutions) and how one can make use of the theoretical characterization in practice.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "C2B-Z6UU1aW", "reviewer": "Reviewer_JuQi", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper analyzes the stability issues in Q learning and SARSA with epsilon greedy exploration. The authors use Differential Inclusion (DI) theory to analyze the behavior of Q learning and SARSA. The authors use numerical examples to illustrate their theory.", "summary_of_the_review": "The technique that this paper introduced is interesting, but since there are several issues in the paper and thus I don't think it qualifies as an ICLR publication.", "strength_and_weaknesses": "Strength:\n\nThe stability issue of Q learning and SARSA is very important. The paper uses a novel technique named Differential Inclusion (DI) theory to study this problem. This technique is not very common in the RL community, and I think it's quite interesting to introduce this technique to the community.\n\nWeakness:\n\n1) Although epsilon-greedy is an important method, it is known that this approach is not a very smart exploration method. Therefore, it would be useful to discuss how to extend this framework to other methods.\n2) The assumption B4 in page 5 seems to be quite strong. I am not sure how to interpret this assumption.\n3) The experiments only use numerical simulations. It would be better to provide empirical evidence in more realistic environments.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9F7KDHaDL24", "reviewer": "Reviewer_svEP", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a new analysis framework based on differential inclusion (DI) theory for analyzing value-based reinforcement learning (RL) methods with discontinuous behavior policy changes (such as Q-learning with an epsilon-greedy behavior.) Using the new framework, the paper provides an explanation of the asymptotic behaviors of both Sarsa(0) and Q-learning with an epsilon-greedy policy and linear function approximation. Finally, the paper discusses several MDP examples and shows how an algorithm’s limiting DI affects its convergence behavior.", "summary_of_the_review": "This paper presents a new framework to analyze the convergence behaviors of algorithms with discontinuous behavior policies and function approximation. This work is likely of interest to those doing RL theory research, and could be of some interest to the larger RL research community as well. Therefore I vote to accept.", "strength_and_weaknesses": "The main strength of this paper is its comprehensive introduction of the new analysis framework that provides previously missing theory on how to explain unexpected behaviors in certain algorithms under approximation.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "4r723G_k6O", "reviewer": "Reviewer_A5T2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work tries to explain the asymptotic behaviors of two well-known approximate RL algorithms, Q-learning and SARSA, with $\\epsilon$-greedy exploration. The theoretical analysis presented in this work uses Differential Inclusion (DI) theory to analyze value-based RL methods with discontinuous behavior policy changes. Numerical examples have also been used to demonstrate the usage of the proposed theoretical result for explaining the limitation of  Q-learning and SARSA algorithms with linear function approximation and $\\epsilon$-greedy exploration. ", "summary_of_the_review": "The theoretical analysis presented in this paper is novel, but there are some parts of the paper that are not totally clear. The most important question that needs to be answered is how we can use the proposed theory in order to overcome or fix the unexpected of the approximate Q-learning and SARSA algorithms with $\\epsilon$-greedy exploration.", "strength_and_weaknesses": "**Strength**\n\n- The explanation of the asymptotic behavior of two well-known approximate RL algorithms, Q-learning and SARSA, with $\\epsilon$-greedy exploration is quite important and constitutes a challenging open problem.\n- Differential Inclusion (DI) theory can be used for analyzing value-based RL methods with discontinuous behavior policy changes.\n- Numerical examples have been used to demonstrate the usage of the proposed theoretical result.\n\n**Weaknesses**\n\n- The intuition behind the usage of the differential Inclusion (DI) theory should be described in a more precise way.\n- The theoretical analysis seems to be more related to the LSTD. Authors should elaborate if the proposed theoretical result can be also applied in the case of the LSTD algorithm.\n- The usage of the proposed theorem for verification of the convergence to the optimal Q-function of the tabular versions of Q-learning and SARSA algorithms need to be examined.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject