CONVERGENT REINFORCEMENT LEARNING WITH FUNCTION APPROXIMATION: A BILEVEL OPTIMIZA-
Year: 2018

Abstract:
We study reinforcement learning algorithms with nonlinear function approximation in the online setting. By formulating both the problems of value function estimation and policy learning as bilevel optimization problems, we propose online Q-learning and actor-critic algorithms for these two problems respectively. Our algorithms are gradient-based methods and thus are computationally efficient. Moreover, by approximating the iterates using differential equations, we establish convergence guarantees for the proposed algorithms. Thorough numerical experiments are conducted to back up our theory.

heading: 1 INTRODUCTION
text: In reinforcement learning (Sutton & Barto, 1998), the agent aims to make optimal decisions by interacting with the environment and learning from the experiences, where the environment is modeled as a Markov Decision Process (MDP). With the recent advancement of deep learning, reinforcement learning has achieved extraordinary empirical success in solving complicated decision making problems, such as the game of Go (Silver et al., 2016; 2017), navigation (Banino et al., 2018), and dialogue systems (Li et al., 2016).
Despite its great empirical success, there exists a gap between the theory and practice of reinforcement learning. Specifically, in terms of theory, most existing works focus on either the tabular case or the case with linear function approximation. In the former case, both the state and action spaces are finite, while in the latter the value function is assumed to be linear in a given feature mapping. Using tools for convex optimization and linear regression, the statistical and computational properties of the reinforcement learning algorithms are well-understood under these restrictive settings. Moreover, when it comes to nonlinear function approximation, theoretical analysis becomes intractable as it involves solving a highly nonconvex statistical optimization problems. Moreover, it is shown in Tsitsiklis & Van Roy (1997) that simple method such as TD(0) might fail to converge when nonlinear value functions are applied. However, using deep learning techniques, methods such as deep Q-network (DQN) (Mnih et al., 2015) and asynchronous advantage actor-critic (A3C) (Mnih et al., 2016) become baseline algorithms for artificial intelligence for practical applications.
To bridge such a gap in DRL, we make the first attempt to study the convergence of online reinforcement learning algorithms with nonlinear function approximation in general. In particular, we propose online Q-learning (Watkins & Dayan, 1992) and actor-critic algorithms with two-timescale updates Konda & Tsitsiklis (2000), i.e., the iterative algorithm consists of two parameters that updates with different learning rates. Although the statistical and computational properties of these methods with linear function approximation are well-studied, convergence of reinforcement learning methods with nonlinear function approximation is fundamentally more challenging due to the lack of convexity. In this case, we can only expect convergence to local minima or stationary points.
Furthermore, we bring both the problems of value function and policy learning under the unified framework of bilevel optimization, which motivates two-timescale updating rules in our algorithms.
Specifically, bilevel optimization problems consist of two subproblems that are intertwined with each other. Such phenomenon appears in both Q-learning and actor-critic algorithms. For Q-learning with function approximation, the updates of the target function (also known as target network for DQN) and the value function are coupled together; the same is the updates of the policy and value function in the actor-critic algorithm. Since the two variables in bilevel optimization have different roles, one servers as the constraint of the other, two-timescale updates appears naturally for these problems. In particular, the parameter of the lower optimization problem needs to be updated using a larger stepsize. In addition, as a byproduct, from the view of bilevel optimization, the target network in DQN appears to be the parameter of the upper level optimization, which justifies the trick of using a target network in DQN.
The analysis of our algorithms utilizes stochastic approximation (Borkar, 2008; Kushner & Yin, 2003), which approximates the asymptotic behavior of the iterates using ordinary differential equations. Specifically, under certain assumptions, we show that the online Q-learning algorithm converges almost surely to a local minimizer of the mean squared Bellman error. In addition, for the actor-critic algorithm, we show that the limit points of the actor and critic updates can be characterized by a set of equations.
Our contributions are three-fold. First, we unify the problems of value function estimation and policy learning using the framework of bilevel optimization, which leads to the online Q-learning and actor-critic algorithms using two-timescale updates. Second, using stochastic approximation, the convergence of the proposed algorithms are established with nonlinear function approximation. Third, as a byproduct, the formulation of Q-learning via bilevel optimization justifies the techniques of target network used in DQN, which can be viewed as the parameter of the upper level optimization subproblem.
Related Work. Our work is closely related to the literature on the convergence of online reinforcement learning algorithms with function approximation. For policy evaluation, most existing works focus on algorithms with linear function approximation. Tsitsiklis & Van Roy (1997) study the convergence of the on-policy TD(λ) algorithm based on temporal-difference (TD) error. To handle off-policy sampling, Maei et al. (2010); Sutton et al. (2009; 2016); Yu (2015); Hallak & Mannor (2017) propose various TD-learning methods with convergence guarantees. Utilizing two-timescale stochastic approximation in Borkar (2008) and strong convexity, they establish global convergence results for the proposed methods. The finite-sample analysis of these methods are recently established in Dalal et al. (2017b;a). Moreover, using a duality formulation, Liu et al. (2015); Du et al. (2017) study the finite-sample performance of TD-learning algorithms with primal-dual updates. As for nonlinear function approximation, to the best of our knowledge, the only convergent algorithm is the nonlinear-GTD algorithm proposed in Bhatnagar et al. (2009a), which is more pertinent to our results. Their analysis also depends on two-timescale stochastic approximation, where the variable in the faster timescale essentially solves a linear equation, thus converges to the global optimum. However, in our problem, both the two variables solves nonconvex problems, which adds more challenge in the analysis. In addition, we mainly consider the problem of Q-learning and actor-critic, whereas their results only focus on policy evaluation. Moreover, their algorithm involves the Hessian of the value function and their theory requires the value function to be three times differentiable, whereas our algorithm only requires the gradient of the value function with less stringent assumptions. Thus, our results are not directly comparable with this work.
Furthermore, for Q-learning and the actor-critic algorithm, existing results all consider linear function approximation. For Q-learning, Melo et al. (2008); Prashanth et al. (2014) study the convergence using stochastic approximation. In addition, the actor-critic algorithm is introduced in Sutton et al. (2000); Konda & Tsitsiklis (2000), which also study its convergence with linear function approximation. Later, Kakade (2002); Peters & Schaal (2008) propose the natural actor-critic algorithm which updates the policy function using natural gradient descent (Amari, 1998). Convergence of actor-critic and natural actor-critic algorithms with linear function approximation are studied in Bhatnagar et al. (2009b; 2008); Castro & Meir (2010); Bhatnagar (2010); Maei (2018).

heading: 2 NOTATION AND BACKGROUND
text: In this section, we first lay out the notation that will be followed throughout this paper and then introduce some background knowledge on reinforcement learning.
We stick to the following notation. For a measurable space with domain S, we denote by B(S) the set of bounded measurable functions on S. Let Lip(S, L) be the set of Lipschitz continuous functions on S with Lipschitz constant L. Let P(S) be the set of all probability measures over S. For any ν ∈M(S) and any measurable function f : S → R, we denote by ‖f‖ν,p the `p-norm of f with respect to measure ν. For an integer k, we use ∆k to denote the probability simplex in Rk, and let [k] = {1, 2, ..., k}.
In reinforcement learning, the problem is modeled by a Markov decision process. A discounted MDP is defined by a tuple (S,A, P,R, p0, γ), where S is the set of states,A is the set of all possible actions, P : S ×A → P(S) is the Markov transition kernel, R : S ×A → R is the reward function, p0 ∈ P(S) is the distribution of the initial state s0, and γ ∈ (0, 1) is the discount factor. At any state s ∈ S, suppose action a ∈ A is executed, we use P (· |s, a) ∈ P(S) to denote the probability distribution of the next state, and let R(s, a) be the the immediate reward. For regularity, we assume that the rewards are uniformly bounded by Rmax. By taking action at at state st for each time step t ≥ 0, the agent receives the discounted cumulative reward R = ∑ t≥0 γ t ·R(st, at).
Moreover, a policy π : S → P(A) is a action selection rule. Specifically, π(a | s) is the probability of selecting action a at state s. We define the state value function and the action value function of policy π as V π(s) = Eπ(R | s0 = s, π) and Qπ(s, a) = Eπ(R | s0 = s, a0 = a), respectively. Here we use Eπ to indicate that the actions {at}t≥1 follow policy π. We define Bellman operator of T π : B(S) → B(S) by T πV (s) = E[r(st, at) + γ · V (st+1) | st = s], where at ∼ π(· | st). By definition, we have V π = T πV π for any policy π. Since T ∗ is γ-contractive, V π is the unique fixed point of T π . The problem of estimating V π for a fixed policy π is called policy evaluation.
Furthermore, in reinforcement learning, the goal is to obtain the policy that yields the maximal cumulative reward in expectation. To this end, we define the optimal value functionQ∗ : S×A → R by Q∗(s, a) = supπ Q
π(s, a),∀(s, a) ∈ S × A, where the supremum is taken over all possible policies. Then it is known that the greedy policy with respect to Q∗ is the optimal policy. To estimate Q∗ with accuracy, most existing methods utilize the fact that Q∗ is the unique fixed point of the Bellman optimality operator T ∗, which is defined by
(T ∗Q)(s, a) =r(s, a) + γ · E [ max a∈A Q(st+1, a) ∣∣ st = s, at = a]. (2.1)
The most well-known method for estimating Q∗ is the Q-learning algorithm (Watkins & Dayan, 1992), based upon a large family of algorithms are derived.
In addition to methods that focus on estimating the value functions, another class of algorithms in reinforcement learning directly search for a good policy over a parametrized policy class {πω : ω ∈ Rp} directly, where ω is the parameter. Specifically, the goal is to maximize J(ω) = Eπω (R) = Es0∼p0 [V πω (s0)]. The basis of these methods are provided by the policy gradient theorem (Baxter & Bartlett, 2000), which states that
(1− γ) · ∇ωJ(ω) = Es∼ρω,a∼πω(· | s)[∇ω log πω(a | s) ·Q πω (s, a)] = Es∼ρθ,a∼πω(· | s) { ∇ω log πω(a | s) · [R(s, a) + γ · V πω (s′)− V πω (s)] } , (2.2)
where s′ ∼ P (· | s, a) is the next state of the MDP given (s, a) ∈ S ×A, and ρω ∈ P(S) is the state occupancy measure of πω , i.e., ρω(s) = (1− γ) · ∑ t≥0 γ
t · Pπω (st = s). We note that (2.2) brings the value function and the policy together. By updating θ using (2.2) with the value function Qπω or V πω estimated using temporal difference learning methods, we obtain the actor-critic algorithms (Konda & Tsitsiklis, 2000).

heading: 3 REINFORCEMENT LEARNING AS BILEVEL OPTIMIZATION
text: As we introduced in the previous section, estimation of the value functions and policy learning are crucial problems of reinforcement learning. In this section, we show that both these two problems can be cast into bilevel optimization. From this view, we establish the Q-learning and actor-critic algorithms with two-timescale updates.
In the unconstrained form, bilevel optimization is formulated as an optimization problem that contain another optimization problem as a constraint. Specifically, it can be written as
x∗ = argmin x∈X F [x, y∗(x)], where y∗(x) = argmin y∈Y G(x, y), (3.1)
where F,G : X ×Y → R are two differentiable functions. Here the challenges in (3.1) are threefold. First, to evaluate the objective function F [x, y∗(x)], one needs to achieve the global minimizer of G(x, y) for each x, which might not be feasible whenG(x, y) is not a convex function of y. Second, even if we are able to obtain y∗(x) and evaluate F [x, y∗(x)] for any x ∈ X , since it is impossible to compute the gradient of y∗(·), minimize F [x, y∗(x)] via gradient-based methods is impossible. In practice, we can only hope for obtaining (x\, y\) ∈ X × Y satisfying
y\ = y∗(x\) and x] = argmin x∈X F (x, y) | y=y\ . (3.2)
Third, in machine learning applications, usually both F and G in (3.1) are computed using largescale datasets. In this situation, it can be highly costly to solve the lower level optimization problem to the exact minimizer. Thus, efficient algorithms have to be robust to the error incurred in solving for y∗(·).
An efficient algorithm that achieves the condition in (3.2) is two-timescale gradient descent, where we simultaneously perform gradient update with respect to both x and y. Specifically, we have
xt+1 ← xt − αt · ∇xF (xt, yt), yt+1 ← yt − βt · ∇yG(xt, yt), (3.3) where the stepsizes {αt, βt}t≥0 satisfy the following two-timescale assumption. Assumption 3.1. We assume that the stepsizes {αt, βt}t≥0 satisfy∑
t≥0 αt = ∑ t≥0 βt =∞, ∑ t≥0 α2t + β 2 t <∞, lim t→∞ αt/βt = 0. (3.4)
That is, in addition to the standard Robbins-Monro condition (Robbins et al., 1951), we have αt/βt → 0, which indicates that {yt}t≥0 updates in a faster pace than {xt}t≥0. This condition gives the name of two-timescale update, and plays a pivotal role in the theoretical analysis.
More rigorously, measured in the faster timescale using {βt}t≥0, the updates in (3.3) converge to the asymptotically stable equilibria of the ODE system {ẋ = 0, ẏ = −∇yG(x, y)}. Thus, {xt, yt}t≥0 converges to some (x\, y\) where y\ is a local minimizer of G(x\, ·). When G(x\, ·) has a unique minimizer, we have y\ = y∗(x\). Thus, under the faster timescale, the updates in (3.3) essentially fix the x variable and let {yt}t≥0 converge to y∗(x) using gradient descent.
Furthermore, to determine the convergence of {xt}t≥0, we need to look into the slower timescale. Since {yt}t≥0 updates in a faster speed under Assumption 3.1, we could safely assume that {yt}t≥0 already converge to y∗(x) for some x ∈ X . In this scenario, the asymptotic behavior of {xt}t≥0 is captured by the ODE ẋ = −∇xF (x, y) | y=y∗(x). Suppose minx F (x, y) has a unique minimizer, denoted by x∗(y), then {xt, yt}t≥0 converges to some (x\, y\) satisfying x\ = x∗(y\), y\ = y∗(x\). This implies that the two-timescale gradient update in (3.3) achieves the condition in (3.2) asymptotically. Moreover, when the minimizers of F (·, y) and G(x, ·) are not unique, using similar analysis, it can be shown that x\ is a local minimizer of minx F (x, y\), and simultaneously y\ is a local minimizer of miny G(x\, y).
In the rest of this section, we apply the above argument to problems in reinforcement learning. In particular, we formulate both value function estimation and policy learning as bilevel optimization problems, which naturally motivates us to propose two-timescale algorithms with convergence guarantees.

heading: 3.1 VALUE FUNCTION ESTIMATION
text: In value function estimation, the goal is to estimate either V π or Q∗ defined in §2 using function approximation. Note that V π and Q∗ are the unique fixed points of Bellman operators T π and T ∗, respectively. Here we mainly focus on Q∗, the results for V π can be similarly obtained by replacing T ∗ in (2.1) by T π .
Let F = {Qθ : S × A → Rd, θ ∈ Rd} be a parametrized function class, where θ is the parameter. Our goal is to find Qθ such that the mean-squared Bellman error (MSBE)
`(θ) = ‖Qθ − T ∗Qθ‖2ρ = E(s,a)∼ρ ({ Qθ(s, a)−R(s, a)− γ · E [ max a′∈A Qθ(s ′, a′) ∣∣ s, a]}2) (3.5) is minimized, where ρ ∈ P(S × A) is probability distribution, and s′ ∼ P (· | s, a) is the next state of the MDP. Note that Q-learning is an off-policy method. To learn Q∗, it is common to obtain sample from the MDP using a behavioral policy πb, which induces a Markov chain on S ×A. Then ρ can be viewed as the stationary distribution of this Markov chain. Furthermore, for simplicity, we assume that drawing i.i.d. samples from ρ is possible, which approximately holds when the Markov chain enjoys rapid mixing properties.
Moreover, notice that in (3.5), the conditional expectation is inside the quadratic function, which is known to cause the issue of “double sampling” (Baird et al., 1995). That is, to obtain an unbiased estimate of the MSBE, given (s, a) ∼ ρ, we need two conditionally independent samples from P(· | s, a), which cannot be satisfied in practice. To avoid this issue, we write MSBE minimization as a bilevel optimization problem
ω = min ω ‖ω − ϑ(ω)‖22 subject to ϑ(ω) = argmin
θ∈Rd
{ L(θ, ω) = ‖Qθ − T ∗Qω‖2ρ } . (3.6)
We note that if there exists a θ∗ such that Qθ∗ = Q∗, then we have ϑ(θ∗) = θ∗, which implies that (ω, θ) = (θ∗, θ∗) is the solution of (3.6). Intuitively, with nonlinear function approximation, the lower level optimization problem minθ L(θ, ω) solves a nonlinear least square regression problem using function class F , where T ∗Qω can be viewed as the response variable. After obtaining ϑ(ω), then for the upper level optimization problem, we directly replace by ϑ(ω). Thus, in the batch setting, solving the bilevel optimization in (3.6) yields the fitted Q-iteration algorithm (Riedmiller, 2005; Munos & Szepesvári, 2008). Specifically, When deep neural networks are used for function approximation, we recover the well-known deep Q-network (DQN) (Mnih et al., 2015), where Qω in (3.6) is the target network. We note that the usage of the target network is a critical trick in DQN, whose mechanism is not fully understood. Therefore, the target network in DQN can be viewed as the parameter of the upper level optimization of the bilevel formulation in (3.6). From the perspective of bilevel optimization, it is natural that the target network needs to be updated in a slower rate, which justifies the empirical practice of DQN that the target network is updated every Ttarget iterations while the Q-network is updated in each iteration.
To obtain an online algorithm, we solve (3.6) via two-timescale gradient update given in (3.3). The update rules are given by ωt+1 ← (1 − αt) · ωt + αt · θt, and θt+1 ← θt − βt · ∇θL(θt, ωt). In addition, we note that∇θL(θ, ω) has an unbiased estimate
[Qθ(s, a)−R(s, a)− γ ·max a′∈A Qω(s ′, a′)] · ∇θQθ(s, a).
Thus, replacing ∇θL(θ, ω) by its estimate, we obtain our online Q-learning algorithm, which is stated in Algorithm 1. Here in line 6 we project the iterate to a compact set X = {x ∈ Rd : ‖x‖2 ≤ RX } for stability, where RX is a sufficiently large constant. It is clear that our algorithm is free from the double sampling issue. Moreover, as we see in §4, this algorithm converges almost surely to ω∗, ϑ(ω∗), where ϑ(ω∗) is a local minimizer of minθ L(θ, ω∗), and ω∗ is close to ϑ(ω∗) up to some error caused by projection.
Finally, we note that Algorithm 1 can be similarly applied to policy evaluation, where we estimate V π using function class {Vθ : S → R, ω ∈ Rd}. In this case, by the definition of T π , we only need to replace δt in line 5 by δt = Vθt(st) − R(st, at) − γ · Vωt(s′t). Moreover, here ρ is set to be the stationary distribution induced by policy π. We defer the algorithm for policy evaluation to §A.
Algorithm 1 Online Q-learning with nonlinear function approximation. 1: Input: Initialization θ0 = ω0 ∈ Θ, stepsizes {αt, βt}t≥0. 2: Output: The sequences {θt}t≥0 and {ωt}t≥0 . 3: for t = 0, 1, 2, . . . do 4: Sample (st, at) ∼ ρ, observe reward R(st, at) and next state s′t. 5: Compute the TD-error δt = Qθt(st, at)−R(st, at)− γ ·maxa∈AQωt(s′t, a). 6: Update the parameters by
ωt+1 = ΠX [(1− αt) · ωt + αt · θt], θt+1 = θt − βt · δt · ∇θQθt(st, at). (3.7) 7: end for

heading: 3.2 THE ACTOR-CRITIC ALGORITHM
text: Now we formulate policy learning as bilevel optimization and obtain the actor-critic algorithm. Let {πω : ω ∈ Rp} be the family of policies and let {Vθ : θ ∈ Rd} be a parametrized family of value functions. Note that the objective in policy learning can be written as J(ω) = Es0∼p0 [V πω (s0)]. We define F (θ, ω) = Es0∼p0 [Vθ(s0)] and consider the bilevel optimization problem
max ω F [ϑ(ω), ω] subject to ϑ(ω) = argmin θ
{ G(θ, ω) = ‖Vθ − T πωVθ‖2ρω } , (3.8)
where ρω is the state-occupancy measure of policy πω . To see the correctness of such a formulation, notice that if V πω ∈ {Vθ, θ ∈ Rd}, then the solution of the lower level optimization problem ϑ(ω) satisfies that Vϑ(ω) = V πθ , which leads to F [ϑ(ω), ω] = J(ω) for all ω ∈ Rp. Thus, we recover the original policy learning problem.
Note that minθ G(θ, ω) is an policy evaluation problem. Directly solving this problem suffers the issue of double sampling. To resolve this issue, as stated above, one need to formulate itself as a bilevel optimization problem. This will result in a three-timescale algorithm for policy learning. However, due to its complexity, instead we consider the TD(0) method, which is a semi-gradient method for policy evaluation (Sutton & Barto, 1998). Specifically, we define
g(θ, ω) = Es∼ρω,a∼πω(· | s) { [R(s, a) + γ · Vθ)(s′)− Vθ(s)] · ∇θVθ(s) } , (3.9)
which can be viewed as a biased estimate of −∇θG(θ, ω). Similar to (3.3), we approximately solve (3.8) via ωt+1 ← ωt +α∇ωF (θt, ωt), and θt+1 ← θt +βt · g(θt, ωt). Moreover, by policy gradient theorem, we have
∇ωF (θ, ω) = Es∼ρω,a∼πω(· | s) { [R(s, a) + γ · Vθ)(s′)− Vθ(s)] · ∇ω log πω(a | s) } . (3.10)
Thus, replacing (3.9) and (3.10) by their sample-based counterparts, we recover the actor-critic algorithm with TD(0) updates,whose details are deferred to §A. Moreover, for algorithmic stability, we project {ωt}t≥0 to Ω = {y ∈ Rd : ‖y‖2 ≤ RΩ} with RΩ sufficiently large.
Furthermore, we note that TD(0) with nonlinear function approximation can diverge in some situations (Tsitsiklis & Van Roy, 1997). In the next section, we given sufficient conditions for the convergence of actor-critic with nonlinear function approximation.

heading: 4 MAIN RESULTS
text: In this section, we establish the convergence results for the algorithm presented in §3. We first consider the online Q-learning algorithm with nonlinear function approximation. Theoretical results for policy evaluation can be similarly obtained, which are omitted for simplicity. We make the following assumption for the online Q-learning. Assumption 4.1. For the online Q-learning algorithm, we assume the following conditions holds.
(i). For any (s, a) ∈ S × A and any θ ∈ Rd, we have |Qθ(s, a)| ≤ Qmax, ‖∇θQθ(s, a)‖2 ≤ Gmax, and ∇θQθ(s, a) is Lipschitz continuous in θ. Here Qmax ≥ Rmax/(1 − γ) and Gmax are two positive constants.
(ii). Let L(θ, ω) be defined in (3.6). For any ω ∈ X , we assume that any local minimizer θ∗ of minθ L(θ, ω) satisfies that∇2θL(θ∗, ω) 0.
Here condition (i) in Assumption 4.1 requires that Qθ(s, a), as a function of θ, satisfies certain smoothness condition. Condition (ii) postulates that any local minimizer of Lω(θ) = L(θ, ω) can be determined using second order optimality condition. This assumption is strictly weaker than the strict saddle property (Ge et al., 2015), which is known to hold for a family of nonconvex functions. Theorem 4.2. Under Assumptions 3.1 and 4.1, if supt≥0 ‖θt‖2 < ∞, then {θt, ωt}t≥0 converges almost surely to some (θ∗, ω∗), where ω∗ ∈ X and θ∗ is a local minimizer of the function L(·, ω∗). In addition, if ‖ω∗‖2 ≤ RX , we have θ∗ = ω∗. Whereas if ‖ω∗‖2 = RX , we have θ∗ = λ · ω∗ for some λ ≥ 1.
To see the intuition of Theorem 4.2, consider the two-timescale gradient updates for the population problem given in (3.6). In the faster timescale, we could fix {ωt}t≥0 at ω∗. Then {θt}t≥0 converges to a local minimizer of L(·, ω), which is denoted by ϑ(ω∗). For the slower timescale, due to the projection ΠX in (3.7), the dynamics of {ωt}t≥0 is characterized by a projected ODE ω̇ = ϑ(ω) − ω + ξω , where ξω(t) is the additional term introduced by projection. Consider any asymptotically stable equilibrium ω∗ of this projected ODE. If ω∗ is in the interior of X , then projection is not activated, and we have ϑ(ω∗) = ω∗. If ω∗ is on the boundary of X , since X is a Euclidean ball, ϑ(ω∗)− ω∗ must be in the same direction as ω∗, which implies that ϑ(ω∗) = λ · ω∗ with λ ≥ 1.
In the following, we lay out the assumption for the actor-critic algorithm. Assumption 4.3. For the actor-critic algorithm, we assume that the following conditions holds.
(i). For any s ∈ S and any θ ∈ Rd, we assume that |Vθ(s)| ≤ Qmax, ‖∇θVθ(s)‖2 ≤ Gmax, and ∇θVθ(s) is Lipschitz continuous. In addition, there exists a constant πmax > 0 such that ‖∇ω log πω(a | s)‖2 ≤ πmax for all (s, a) ∈ S ×A and ω ∈ Ω.
(ii). For function g(θ, ω) defined in (3.9), we assume that for each ω ∈ Ω, the ODE θ̇(t) = g[θ(t), ω] has a local asymptotically stable equilibrium ϑ(ω). Moreover, ϑ(·) is Lipschitz continuous in a neighborhood of ω.
The first condition in Assumption 4.3 is parallel to that in Assumption 4.1. This condition ensures that both the value function and the policy function are regular. More importantly, as shown in §C.2, under the faster timescale, we could fix {ωt}t≥0 at some ω∗ ∈ Ω, and {θt}t≥0 converges to a stable equilibrium of ODE θ̇ = g(θ, ω∗). Thus, condition (ii) ensures that this equilibrium, as a function of ω, is locally Lipschitz. We note that condition (ii) is more restrictive compared with the second condition in the previous assumption. The reason is that TD(0) update for the critic is not a gradient step, i.e., g(θ, ω) is not equal to ∇θG(θ, ω). Thus, {θt}t≥0 cannot converge to a local minimizer of G(·, ω). Now we present the convergence result for the actor-critic algorithm. Theorem 4.4. Under Assumptions 3.1 and 4.3, if supt≥0 ‖θt‖2 < ∞, {θt, ωt} converges to some {ϑ(ω∗), ω∗}, where ϑ(ω∗) is an asymptotically stable equilibrium of ODE θ̇ = g(θ, ω∗). Moreover, if ‖ω∗‖2 < RΩ, we have ∇ωF [ϑ(ω∗), ω∗] = 0. Whereas if ‖ω∗‖2 = RΩ, then there exists λ ≥ 0 such that∇ωF [ϑ(ω∗), ω∗] = λ · ω∗.
Similar to Theorem 4.2, to determine the convergence of {ωt}t≥0, we consider the slower timescale, under which we have the projected ODE ω̇ = ∇ωF [ϑ(ω), ω] + ξω . By studying the equilibrium of this ODE, we obtain the above theorem. An interesting case is that when ‖ω∗‖2 < RΩ, we have g(θ∗, ω∗) = 0 and ∇ωF (θ∗, ω∗) = 0, where θ∗ = ϑ(ω∗). Intuitively, this implies that actor-critic converges to a local Nash equilibrium.

heading: 5 NUMERICAL EXPERIMENTS
text: In this section, we evaluate the performance of our online Q-learning and actor-critic algorithms using OpenAI Gym (Brockman et al., 2016), which is a standard testbed for reinforcement learning.
Online Q-learning. First, we present the results for Algorithm 1 on Acrobot and MountainCar, which are two classical control tasks. The value functions for Acrobot and MountainCar are neural networks with one and two hidden layers, respectively, where all hidden layers have 64 neurons. To corroborate with our theory, in the experiments, we fix βt = 10−3 for all t ≥ 0 and let αt be various constants. We train the neural networks using minibatch stochastic gradient descent, where the batch size is 32. The results are plotted in Figure 1, where three independent experiments are performed for each setting. Here each curve is the mean value µ of the results in the same setting, together with the shadow representing the interval [µ − σ/2, µ + σ/2], where σ is the standard deviation. Also, in order to have a better visualization, we use a uniform moving average method with window size 20000 frames to smooth out the curves.
As shown in Figure 1, for both Acrobot and MountainCar, when αt < βt (green and blue lines), the reward grows gradually and approaches the maximum reward. Whereas if αt > βt (dark yellow and black lines), the reward finally approaches the minimum. This sharp transition justifies the validity of using two-timescale updates with βt αt in the online Q-learning.
Two-timescale actor-critic algorithm. We also test the actor-critic algorithm on two Atari 2600 games: Pong and Breakout. Here we implement our algorithm based on the A3C framework (Mnih et al., 2016) with 32 asynchronous agents in parallel. In these experiments, we fix stepsize of the actor to αt = 10−4 and let the stepsize of the actor βt be various constants. Similar to the previous experiment, we plot the results in Figure 2 based on three independent trials, which is deferred to the appendix.
As shown in Figure 2, for those settings with a larger critic stepsize βt (green and blue lines), the reward gradually converges to its maximum, while for others with a smaller critic stepsize (dark yellow and black lines), the rewards stay at a very low level. This agrees with our claim in Theorem 4.4 that the critic proceeds in a faster speed than the actor.

heading: 6 CONCLUSION
text: We study online reinforcement learning with nonlinear function approximation in general. Using the unified framework of bilevel optimization, we propose online first-order algorithms for both value function estimation and policy learning. Moreover, using stochastic approximation results, we show that the asymptotic behavior of the algorithms are captured by ordinary differential equations. Finally, we perform thorough empirical studies in support of our theory.

heading: A THE POLICY EVALUATION AND ACTOR-CRITIC ALGORITHMS
text: Algorithm 2 Online policy evaluation with nonlinear function approximation. 1: Input: Initialization θ0 = ω0 ∈ Θ, stepsizes {αk}, {βk}, and sampling distribution ρ ∈
∆(S ×A). 2: Output: The sequences {θt}t≥0 and {ωt}t≥0 . 3: for t = 0, 1, 2, . . . do 4: Sample (st, at) ∼ ρ, observe reward R(st, at) and next state s′t. 5: Compute the TD error δt = Qθt −Rt − γ ·maxa∈AQωt(S′t, a). 6: Update the function estimates by
θt+1 = ΠΩ[(1− αt) · ωt + αt · θt], θt+1 = θt − βt · δt · ∇θQθt(St, At). (A.1)
7: end for
Algorithm 3 The actor-critic algorithm with nonlinear function approximation. 1: Input: Initialization ω0 ∈ Rd and θ0 ∈ Rp, stepsizes {αt, βt}t≥0. 2: Output: The sequences {θt}t≥0 and {ωt}t≥0 . 3: for t = 0, 1, 2, . . . do 4: Sample st ∼ ρωt , take action at ∼ πωt(· | st), observe reward R(st, at) and the next state s′t.
5: Compute the TD-error δt = R(st, at) + γ · Vθt(s′t)− Vθt(st). 6: Update the parameters by
ωt+1 = ΠΩ[ωt + αt · ∇ω log πωt(at | st) · δt], θt+1 = θt + βt · δt · ∇θVθt(st). (A.2)
7: end for

heading: B ADDITIONAL FIGURES OF NUMERICAL EXPERIMETNS

heading: C PROOFS OF THE MAIN RESULTS
text: In this section, we lay out the proofs of Theorems 4.2 and 4.4.
C.1 PROOF OF THEOREM 4.2
Proof. Our proof consists of two steps. The first step consists of the analysis under the faster timescale, where we show that in this case we could fix {ωt}t≥0 at some ω∗ ∈ X and only focus on {θt}t≥0. In the second step, we look into the slower timescale, which yields the convergence result for {ωt}t≥0 and completes the proof.
Step 1. Faster timescale. We first consider the convergence of {θt, ωt}t≥1 in the faster timescale. Using stochastic approximation, we will show that the sequence {θt}t≥0 defined in (3.7) tracks a local minimizer of the lower level optimization.
To begin with, for notational simplicity, we define
δt = Qθt(st, at)− r(st, at)− γ ·Qωt(s′t, a′t), φt = ∇θQθt(st, at), for all t ≥ 0, where a′t = argmaxa∈AQθt(s′t, a). Then the updating rules in Algorithms 1 reduce to
ωt+1 ← ΠX [ ωt + αt · (θt − ωt) ] , θt+1 ← θt − βt · δt · φt, (C.1)
where {αt, βt}t≥0 are the stepsizes, and ΠX is the projection operator onto set X , which is assumed to be a closed Euclidean ball with radiusRω . In addition, letF (1)t = σ({θ`, ω`}`≤t) be the σ-algebra generated by the parameter iterates until time t. By definition, θt and ωt are F (1)t -measurable for any t ≥ 1. Furthermore, for any θ ∈ Rd and ω ∈ Rp, we define
h(θ, ω) = E(s,a)∼ρ { [Qθ(s, a)− (T ∗Qω)(s, a)] · ∇θQθ(s, a) } , (C.2)
Thus, by the definition of the Bellman optimality operator in , for any t ≥ 0, we have E[δtφt | F (1)t ] = h(θt, ωt). This implies that {ζt}t≥0 defined by ζt = h(θt, ωt) − δt · φt is a martingale difference sequence with respect to the filtration {F (1)t }t≥0.
Moreover, for any compact set X ⊆ Rd, we denote by CX (x) the outer normal cone of X at x ∈ X . That is, CX (x) = {u ∈ Rd : u>(y − x) ≤ 0,∀y ∈ X}. In particular, if x is in the interior of X , then CX (x) is empty. Moreover, since we assume X is an Euclidean ball with radius RX , for any x in the boundary of X , denoted by ∂X , we have CX (x) = {λ · x : λ ≥ 0}. Using the notion of the outer normal cone, the first equation in (C.1) can be written as
ωt+1 = ωt + αt · (θt − ωt + ξt), (C.3) where ξt ∈ −CX (ωt+1) is the correction term caused by projection onto X . Since (1−αt) ·ωt ∈ X and ωt+1 is the projection of ωt + αt · (θt − ωt), we have
‖ξt‖2 = 1/αt · inf y∈X ‖ωt + αt · (θt − ωt)− y‖2 ≤ ‖θt‖2 (C.4)
for all t ≥ 0. Then, writing the two equations in (C.1) together, we have( θt+1 ωt+1 ) = ( θt ωt ) + βt · ( −h(θt, ωt) + ζt αt/βt · (θt − ωt + ξt) ) . (C.5)
In the following, we apply the result on ODE approximation to (C.5). First note that under Assumption 4.1, |Qθ(s, a)|, ‖∇θQθ(s, a)‖2 are bounded by Qmax and Gmax, respectively. This implies that implies that ‖δt · φt‖ is bounded by 2Qmax · Gmax for all t ≥ 1. Thus, {ζt}t≥0 is a bounded martingale sequence. Then there exist an absolute constant C > 0 such that
E[‖ζt‖22 | Ft] ≤ C for all t ≥ 1.
Moreover, let MT = ∑T t=0 βt · ζt for any T ≥ 0. Since ∑ t≥0 β 2 t < ∞, by the Martingale convergence theorem (Proposition VII-2-3(c) on page 149 of Neveu (1975)), {MT }T≥0 converges almost surely. Additionally, MT is square integrable with E‖MT ‖22 ≤ C · ∑ t≥0 β 2 t . Thus, for any
> 0, by Doob’s martingale inequality (Doob, 1953), we have P (
sup N≥T
‖MN −MT ‖ ≥ ) ≤ supN≥T E[‖MN −MT ‖22] 2 ≤ 2C2 ∑ t≥T β 2 t 2 ,
which converges to zero as T goes to infinity. Furthermore, under Assumption 3.1 and the assumption that supt≥0 ‖θt‖2 < ∞, it holds that αt/βt · (θt − ωt + ξt) = 0 as t goes to infinity. Besides, since both ∇θQθ(s, a) and Qθ(s, a) are bounded and Lipschitz continuous under Assumption 4.1, h(θ, ω) defined in (C.2) is Lipschitz in both θ and ω.
Now we apply Theorem D.2 to sequence {(θt, ωt)}t≥0, which implies that the asymptotic behavior of {(θt, ωt)}t≥0 converges almost surely to the set of asymptotically stable equilibria of the ODE
θ̇ = −h(θ, ω), ω̇ = 0. (C.6) Specifically, the set of asymptotically stable equilibria of the ODE in (C.6), denoted by K1, is
K1 = { (θ∗, ω∗) : ω∗ ∈ X , h(θ∗, ω∗) = 0 } . (C.7)
For any ω ∈ Rd, we denote Lω(θ) = L(θ, ω) = ‖Qθ − T ∗Qω‖2ρ. Since h(θ, ω) = ∇θLω∗(θ), the asymptotically stable equilibrium of ODE θ̇ = −∇θLω∗(θ) is the local minima of Lω∗(θ).
Therefore, for the analysis under the faster timescale, essentially we can fix {ωt}t≥0 at some ω∗ and consider solely the asymptotic behavior of {θt}t≥0. In this case, {θt}t≥0 converges almost surely to a local minimizer θ∗ of Lω∗(·). We note that Lω∗(·) may have multiple local minimizers. In this case, the local minimizer that {θt}t≥0 converges to is determined by the basin of attraction that {θt}t≥0 enters. Moreover, note that under Assumption 4.1, ∇2θLω(·) is positive definite at all its local minima, which implies that the set of all local minima of Lω∗(·) is a disjoint set.
Consider the equation ∇θLω∗(θ) = 0. Note that θ = θ∗ is a solution. Besides, by the continuity of ∇2θLω(·), there exists a open neighborhood Uθ of θ∗ and a positive number CL such that ∇2θLω∗(θ) CL · Id ∀θ ∈ Uθ. By Lipschitz implicit function theorem (Dontchev & Hager, 1994), there exist a neighborhood U of θ∗, a neighborhood V of ω∗, and a mapping ϑ : V → U such that ϑ(ω∗) = θ∗. In addition, ϑ is Lipschitz continuous and satisfies∇θL(θ, ω)|θ=ϑ(ω) = 0 for all ω ∈ V .
Thus, we show that, in the faster timescale, {θt, ωt}t≥0 converges almost surely to [ϑ(ω∗), ω∗], where ω∗ ∈ X and ϑ is Lipschitz continuous.
Step 2. Slower timescale.
Note that (C.7) cannot characterize the convergence of {ωt}t≥0. Now we look into the dynamics in the slower timescale for a finer characterization. Recall that the update rule of the {ωt}t≥0 is given in (C.3). For ease of presentation, we define σ-field F (2)t = σ({ω`}`≤t) for all t ≥ 0. b In addition, we define
ψt = E [ (θt − ωt) | F (2)t ] − [(ϑ(ωt)− ωt] = E [ θt | F (2)t ] − ϑ(ωt). (C.8)
Then (C.3) becomes ωt+1 = ωt + αt · [(ϑ(ωt)− ωt] + αt · (ψt + ξt), where ξt ∈ −CX (ωt+1).
As we have shown in the first step of the proof, ϑ(ωt) − θt converges to zero as t goes to infinity, where the mapping ϑ : Rd → Rd is Lipschitz continuous. In addition, since supt≥0 ‖θt‖2 is finite, ψt defined in (C.8) is uniformly bounded for all t ≥ 0.
Now we apply the Kushner-Clark lemma (Kushner & Clark, 1978, see also Theorem E.2 in §E for details.) to sequence {ωt}t≥0, it holds that {θt}t≥1 converges almost surely to the set of asymptotically stable equilibria of the ODE
ω̇ = ϑ(ω)− ω + ξω, ξω(t) ∈ −CX (ω(t)), (C.9) where the function ξω appears due to the projection in (C.11). Recall that X is a Euclidean ball with radius RX . For any asymptotically stable equilibrium ω∗ of (C.9), if ω∗ is in the interior of X , we have CX (ω∗) = 0, which implies that ω∗ = ϑ(ω∗). In this case, sequence {(θt, ωt)}t≥1 converges almost surely to (ω∗, ω∗), which satisfies that
E(s,a)∼ρ { [Qω∗(s, a)− (T ∗Qω∗)(s, a)] · ∇θQω∗(s, a) } = 0.
Meanwhile, if ω∗ ∈ X , we have ϑ(ω∗)− ω∗ ∈ CX (ω∗), which implies that there exists λ > 0 such that ϑ(ω∗) = λ · θ∗. Thus, {(θt, ωt)}t≥1 converges almost surely to (λ · ω∗, ω∗). Therefore, we conclude the proof of Theorem 4.2.
C.2 PROOF OF THEOREM 4.4
Proof. The proof is similar to that of Theorem 4.2 in §C.1. We prove the theorem in two steps, considering the faster and slower timescales seperately.
Step 1. Faster timescale. We first consider the convergence of {θt, ωt}t≥1 in the faster timescale. Using stochastic approximation, we will show that the critic sequence {θt}t≥0 converges to an asymptotically stable equilibrium of ODE θ̇ = g(θ.ω∗) for some ω∗ ∈ Ω.
First recall that, for any t ≥ 0, we have st ∼ ρωt , at ∼ πωt(· | st), and s′t ∼ P (· | st, at). To simplify the notation, we define
δt = Vθt(st)− r(st, at)− γ · Vθt(s′t), φt = ∇θVθt(st), At = ∇ω log πωt(at | st). (C.10)
Using these terms, the updating rules in Algorithm 3 become ωt+1 ← ΠΩ [ ωt + αt · δt ·At ] , θt+1 ← θt + βt · δt · φt, (C.11)
where {αt, βt}t≥0 are the stepsizes, and ΠΩ is the projection operator onto Ω. In addition, under Assumption 4.3, we have |Vθ(s)| ≤ Vmax and ‖∇ω log πω(a | s)‖2 ≤ πmax. Thus δt and At defined in (C.10) satisfy |δt| ≤ 2Vmax and ‖At‖ ≤ πmax for all t ≥ 1. Combining (C.11) and Assumption 3.1, this implies that αt/βt · δt ·At converges to zero as t goes to infinity.
Moreover, let F (1)t = σ({θ`, ω`}`≤t). Recall that we define function g(θ, ω) in (3.9). To simplify the notation, let h(θ, ω) = ∇ωF (θ, ω, which is defined in (3.10). Then by (C.10), we have
E [ δt · φt | F (1)t ] = g(θt, ωt), E [ δt ·At | F (1)t ] = h(θt, ωt), (C.12)
which implies that {ζt}t≥0 is a martingale difference sequence, where we define ζt = δt · φt − g(θt, ωt) for all t ≥ 0. Moreover, under Assumption 4.3, we have ‖δt ·φt‖2 ≤ 2Vmax ·Gmax, which implies that there exists an absolute constant C such that E[‖ζt‖22] < C. Therefore, similar to the proof of Theorem 4.2 in §C.1, by applying Theorem D.2, we obtain that, in the faster timescale, sequence {θt, ωt}t≥0 converges almost surely to the asymptotically stable equilibria of ODE system {θ̇ = g(θ, ω), ω̇ = 0}. Under Assumption 4.3, this implies that {ωt}t≥0 converges to some ω∗, while {θt}t≥0 converges to a local asymptotically stable equilibrium θ∗ = ϑ(ω∗). Moreover, ϑ : Rp → Rp is Lipschitz continuous in a open neighborhood of ω∗.
Step 2. Slower timescale. In the sequel, we characterize the convergence of {θt, ωt}t≥1 under the slower timescale. To begin with, we define F (2)t = σ({ω`}`≤t) for all t ≥ 0. In addition, we define
ψ (1) t = −δt ·At + E [ δt ·At | F (2)t ] , ψ (2) t = −E[δt ·At | F (2) t ] + h[θt, ω(θt)], (C.13)
where function g is defined in (3.9),At and φt are defined in (C.10). Since ‖δt·At‖2 ≤ 2Vmax·Gmax, {ψ(1)t }t≥1 is a bounded martingale difference sequence. Moreover, since F (2) t ⊆ F (1) t , by the tower property and (C.12), we have
E[δt ·At | F (2)t ] = E [ E(δt ·At | F (1)t ) ∣∣F (2)t ] = E[h(θt, ωt) ∣∣F (2)t ]. Using the notation in (C.13), the primal update in (C.11) can be written as
ωt+1 = ΠΩ [ ωt + αt · h[ωt, ϑ(ωt)] + αt · ψ(1)t + αt · ψ (2) t ] , (C.14)
where ϑ(ω∗) is a local asymptotically stable attractor of ODE θ̇ = h(θ, ω∗). Moreover, under Assumption 4.3, ∇θVθ(s) and ∇ω log πω(a | s) are bounded, which implies that
‖h(θ(1), ω)− h(θ(2), ω)‖ ≤ 2Gmax · πmax
for any θ(1), θ(2) ∈ Rd and any ω ∈ Ω. Then, by Cauchy-Schwarz inequality, we have ‖ψ(2)t ‖2 ≤ E {∥∥h(θt, ωt)− h[ϑ(ωt), ωt]∥∥2 ∣∣F (2)t } ≤ 2Gmax · πmax · E[‖θt − ϑ(ωt)‖2 ∣∣F (2)t ], which tends to zero as t goes to infinity. As shown in the first step of the proof, ϑ(ωt)−ωt converges to zero as t goes to infinity.
Furthermore, we define WT = ∑T t=1 αt · ψ (1) t ∈ Rd for any T ≥ 1. Since ∑ t≥1 α 2 t <∞ and ψ (1) t is bounded, {WT }T≥1 is a square-integrable martingale sequence, which converges almost surely by the Martingale convergence theorem (Neveu, 1975). Moreover, Doob’s martingale inequality (Doob, 1953) implies that
lim T→∞
P (
sup N≥T ‖WN −WT ‖ ≥ ) ≤ lim T→∞ supN≥T E[‖WN −WT ‖22] 2 ≤ lim T→∞ 2C2 ∑ t≥T α 2 t 2 = 0.
Finally, applying by the Kushner-Clark lemma (Kushner & Clark, 1978) to sequence {ωt}t≥0, it holds that {ωt}t≥0 converges almost surely to the set of asymptotically stable equilibria of the ODE
ω̇ = h[ϑ(ω), ω] + ξω, ξω(t) ∈ −CΩ(ω(t)), (C.15) where CΩ(ω) is the outer normal cone of Ω at ω. Recall that we assume that Ω is a Euclidean ball with radius RΩ. Thus, for any asymptotically stable equilibrium ω∗ of (C.9), if ω∗ is in the interior of Ω, i.e., ‖ω∗‖ < RΩ, we have h[ϑ(ω∗), ω∗] = 0. Additionally, if ‖ω∗‖2 = RΩ, then there exists λ ≥ 0 such that h[ϑ(ω∗), ω∗] = λ · ω∗. Therefore, we conclude the proof of Theorem 4.4.

heading: D BACKGROUND ON STOCHASTIC APPROXIMATION
text: We first present a fundamental result for stochastic approximation which is obtained from Borkar (2008). Consider a sequence of iterations in Rd
xt+1 = xt + γt · [G(xt) +Mt+1], t ≥ 0, x0 ∈ Rd. (D.1)
Here G : Rd → Rd is a deterministic mapping, Mt+1 ∈ Rd is a random vector, and γt > 0 is the stepsize. Assumption D.1. We make the following assumption on the iteration (D.1).
• Function G : Rd → Rd is Lipschitz continuous. • The stepsizes {γt}t≥0 satisfies ∑ t≥0 γt =∞ and ∑ t≥0 γ 2 t <∞;
• Random vectors {Mt}t≥0 is a martingale difference sequence. That is, M0 = 0, E[Mt+1 |xτ ,Mτ , τ ≤ t] = 0. Moreover, we assume that there exists some K > 0 such that
E ( ‖Mt+1‖2 |xτ ,Mτ , τ ≤ t ) ≤ K · (1 + ‖xt‖2).
Then the asymptotic behavior of the {xt}t≥0 in (D.1) is characterized by ODE ẋ = G(x) (D.2)
Suppose Eq. (D.2) has a unique globally asymptotically stable equilibrium x∗, we then have the following two theorems. Theorem D.2. Under Assumption D.1, if supt ‖xt‖2 <∞ almost surely, we have xt → x∗ almost surely. Theorem D.3. Under Assumption D.1, suppose
lim c→∞
G(cx)
c = G∞(x)
exists uniformly on compact sets for some G∞ ∈ C(Rn). If the ODE ẏ = G∞(y) has origin as the unique globally asymptotically stable equilibrium, then we have
sup t ‖xt‖ <∞ almost surely.

heading: E KUSHNER-CLARK LEMMA
text: We state here the well-known Kushner-Clark Lemma (Kushner & Clark, 1978; Metivier & Priouret, 1984; Prasad et al., 2014) in the sequel.
Let Γ be an operator that projects a vector onto a compact set X ⊆ RN . Define a vector Γ̂(·) as
Γ̂[h(x)] = lim 0<η→0
{ Γ[x+ ηh(x)]− x
η
} ,
for any x ∈ X and with h : X → RN continuous. Consider the following recursion inN dimensions xt+1 = Γ { xt + γt[h(xt) + ξt + βt] } . (E.1)
The ODE associated with (E.1) is given by
ẋ = Γ̂[h(x)]. (E.2)
Assumption E.1. We make the following assumptions:
• h(·) is a continuous RN -valued function.
• The sequence {βt}, t ≥ 0 is a bounded random sequence with βt → 0 almost surely as t→∞.
• The stepsizes γt, t ≥ 0 satisfy γt → 0 as t→∞ and ∑ t γt =∞.
• The sequence ξt, t ≥ 0 satisfies for any > 0
lim t
P ( sup n≥t ∥∥∥∥ n∑ τ=t γτξτ ∥∥∥∥ 2 ≥ ) = 0.
Then the Kushner-Clark Lemma says the following.
Theorem E.2. Under Assumption E.1, suppose that the ODE (E.2) has a compact set K∗ as its set of asymptotically stable equilibria. Then xt in (E.1) converges almost surely to K∗ as t→∞.

Review summaries:
The paper casts the problems of value learning and policy optimization, which can be problematic the non-linear setting, into the bilevel optimization framework. It proposes two novel algorithms with convergence guarantees. Although other works with similar guarantees exist, these algorithms are very appealing for their simplicity. A limited empirical evaluation is provided for the value-based method in Acrobot and Mountain Car and in the Atari games Pong and Breakout for the proposed bilevel Actor Critic.

This paper interprets the fitted Q-learning, policy evaluation and actor-critic as a bi-level optimization problem. Then, it uses two-timescale stochastic approximation to prove their convergence under nonlinear function approximation. It provides interesting view of the these existing popular reinforcement learning algorithms that is widely used in DRL. However, there are several points to be addressed in the revision, which are mainly in some of its claims.