Title: CONVERGENT REINFORCEMENT LEARNING WITH FUNCTION APPROXIMATION: A BILEVEL OPTIMIZA-TION PERSPECTIVE

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.

1. INTRODUCTION:

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

2. NOTATION AND BACKGROUND:

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 R k , 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, p 0 , γ), 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, p 0 ∈ P(S) is the distribution of the initial state s 0 , 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 R max . By taking action a t at state s t for each time step t ≥ 0, the agent receives the discounted cumulative reward R = t≥0 γ t • R(s t , a t ).

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 | s 0 = s, π) and Q π (s, a) = E π (R | s 0 = s, a 0 = a), respectively.

Here we use E π to indicate that the actions {a t } t≥1 follow policy π. We define Bellman operator of

T π : B(S) → B(S) by T π V (s) = E[r(s t , a t ) + γ • V (s t+1 ) | s t = s], where a t ∼ π(• | s t ).

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 function Q * : 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(s t+1 , a) s t = s, a t = 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 {π ω : ω ∈ R p } directly, where ω is the parameter. Specifically, the goal is to maximize

J(ω) = E πω (R) = E s0∼p0 [V πω (s 0 )].

The basis of these methods are provided by the policy gradient theorem (Baxter & Bartlett, 2000) , which states that

(1 -γ) • ∇ ω J(ω) = E s∼ρ ω ,a∼πω(• | s) [∇ ω log π ω (a | s) • Q πω (s, a)] = E s∼ρ θ ,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 πω (s t = 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) .

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 when G(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

EQUATION

) 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 α 2 t + β 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 {y t } t≥0 updates in a faster pace than {x t } 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 { ẋ = 0, ẏ = -∇ y G(x, y)}. Thus, {x t , y t } 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 {y t } t≥0 converge to y * (x) using gradient descent.

Furthermore, to determine the convergence of {x t } t≥0 , we need to look into the slower timescale. Since {y t } t≥0 updates in a faster speed under Assumption 3.1, we could safely assume that {y t } t≥0 already converge to y * (x) for some x ∈ X . In this scenario, the asymptotic behavior of {x t } t≥0 is captured by the ODE ẋ = -∇ x F (x, y) | y=y * (x) . Suppose min x F (x, y) has a unique minimizer, denoted by x * (y), then {x t , y t } 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 min x F (x, y ), and simultaneously y is a local minimizer of min y 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.

3.1. VALUE FUNCTION ESTIMATION:

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 → R d , θ ∈ R d } 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 θ ρ = 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 ω ω -ϑ(ω) 2 2 subject to ϑ(ω) = argmin θ∈R d 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 & Szepesvá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 T target 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 ∈ R d : x 2 ≤ R X } for stability, where R X 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, ω ∈ R d }.

In this case, by the definition of T π , we only need to replace δ t in line 5 by

δ t = V θt (s t ) -R(s t , a t ) -γ • 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: Compute the TD-error

Initialization θ 0 = ω 0 ∈ Θ,

δ t = Q θt (s t , a t ) -R(s t , a t ) -γ • max a∈A Q ωt (s t , a). 6:

Update the parameters by

ω t+1 = Π X [(1 -α t ) • ω t + α t • θ t ], θ t+1 = θ t -β t • δ t • ∇ θ Q θt (s t , a t ).

(3.7) 7: end for

3.2. THE ACTOR-CRITIC ALGORITHM:

Now we formulate policy learning as bilevel optimization and obtain the actor-critic algorithm. Let {π ω : ω ∈ R p } be the family of policies and let {V θ : θ ∈ R d } be a parametrized family of value functions. Note that the objective in policy learning can be written as

J(ω) = E s0∼p0 [V πω (s 0 )]. We define F (θ, ω) = E s0∼p0 [V θ (s 0 )] 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 θ , θ ∈ R d }, then the solution of the lower level optimization problem ϑ(ω) ) , ω] = J(ω) for all ω ∈ R p . Thus, we recover the original policy learning problem.

satisfies that V ϑ(ω) = V π θ , which leads to F [ϑ(ω

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

EQUATION

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 (θ, ω) = E s∼ρ ω ,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 ∈ R d : 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.

4. MAIN RESULTS:

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 θ ∈ R d , we have

|Q θ (s, a)| ≤ Q max , ∇ θ Q θ (s, a) 2 ≤ G max , and ∇ θ Q θ (s, a) is Lipschitz continuous in θ.

Here Q max ≥ R max /(1 -γ) and G max 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 sup t≥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 ≤ R X , we have θ * = ω * . Whereas if ω * 2 = R X , 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:

θ ∈ R d , we assume that |V θ (s)| ≤ Q max , ∇ θ V θ (s) 2 ≤ G max ,

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 sup t≥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.

5. NUMERICAL EXPERIMENTS:

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. Here we set β t = 10 -3 for both problems. In addition, for Acrobot, we let α t be one of {10 -2 , 8 • 10 -3 , 3 • 10 -4 , 10 -4 }. For or MountainCar we set α t to be one of {0.7, 0.5, 5 • 10 -4 , 10 -4 }.

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.

6. CONCLUSION:

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.

A THE POLICY EVALUATION AND ACTOR-CRITIC ALGORITHMS:

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 (s t , a t ) ∼ ρ, observe reward R(s t , a t ) and next state s t .

5::

Compute the TD error

δ t = Q θt -R t -γ • max a∈A Q ωt (S t , a).

6::

Update the function estimates by Compute the TD-error

θ t+1 = Π Ω [(1 -α t ) • ω t + α t • θ t ], θ t+1 = θ t -β t • δ t • ∇ θ Q θt (S t , A t ). (A.

δ t = R(s t , a t ) + γ • V θt (s t ) -V θt (s t ). 6:

Update the parameters by 

ω t+1 = Π Ω [ω t + α t • ∇ ω log π ωt (a t | s t ) • δ t ], θ t+1 = θ t + β t • δ t • ∇ θ V θt (s t ). (A.

C PROOFS OF THE MAIN RESULTS:

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 (s t , a t ) -r(s t , a t ) -γ • Q ωt (s t , a t ), φ t = ∇ θ Q θt (s t , a t ),

for all t ≥ 0, where a t = argmax a∈A Q θ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 radius R ω . In addition, let F

(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 θ ∈ R d and ω ∈ R p , 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 ≥ we have

EQUATION

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 ⊆ R d , we denote by C X (x) the outer normal cone of X at x ∈ X . That is, C X (x) = {u ∈ R d : u (y -x) ≤ 0, ∀y ∈ X }. In particular, if x is in the interior of X , then C X (x) is empty. Moreover, since we assume X is an Euclidean ball with radius R X , for any x in the boundary of X , denoted by ∂X , we have C X (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 ∈ -C X (ω 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 Q max and G max , respectively. This implies that implies that δ t • φ t is bounded by 2Q max • G max 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 2 2 | F t ] ≤ C for all t ≥ 1.

Moreover, let M T = 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) ), {M T } T ≥0 converges almost surely. Additionally, M T is square integrable with E M T 2 2 ≤ C • t≥0 β 2 t . Thus, for any > 0, by Doob's martingale inequality (Doob, 1953) , we have

P sup N ≥T M N -M T ≥ ≤ sup N ≥T E[ M N -M T 2 2 ] 2 ≤ 2C 2 t≥T β 2 t 2

, which converges to zero as T goes to infinity. Furthermore, under Assumption 3.1 and the assumption that sup t≥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 K 1 , is

K 1 = (θ * , ω * ) : ω * ∈ X , * , ω * ) = 0 . (C.7) For any ω ∈ R d , 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

C L such that ∇ 2 θ L ω * (θ) C L • I d ∀θ ∈ 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 ∈ -C X (ω 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 ϑ : R d → R d is Lipschitz continuous. In addition, since sup t≥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) ∈ -C X (ω(t)), (C.9)

where the function ξ ω appears due to the projection in (C.11). Recall that X is a Euclidean ball with radius R X . For any asymptotically stable equilibrium ω * of (C.9), if ω * is in the interior of X , we have C X (ω * ) = 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 ϑ(ω * ) -ω * ∈ C X (ω * ), 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 s t ∼ ρ ωt , a t ∼ π ωt (• | s t ), and s t ∼ P (• | s t , a t ). To simplify the notation, we define

δ t = V θt (s t ) -r(s t , a t ) -γ • V θt (s t ), φ t = ∇ θ V θt (s t ), A t = ∇ ω log π ωt (a t | s t ). (C.10)

Using these terms, the updating rules in Algorithm 3 become 

EQUATION

= σ({θ , ω } ≤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 ] < 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, ϑ : R p → R p is Lipschitz continuous in a open neighborhood of ω * .

EQUATION

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

EQUATION

t = -E[δ t • A t | F (2) t ] + h[θ t , ω(θ t )], (C.13)

where function g is defined in (3.9), A t and φ t are defined in (C.10). Since

EQUATION

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 • A t | F (2) t ] = E E(δ t • A t | 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 , 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.

ω t+1 = Π Ω ω t + α t • h[ω t ,

Furthermore, we define W T = T t=1 α t • ψ

(1) t ∈ R d for any T ≥ 1. Since t≥1 α 2 t < ∞ and ψ

(1) t is bounded, {W T } 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 W N -W T ≥ ≤ lim T →∞ sup N ≥T E[ W N -W T 2 2 ] 2 ≤ lim T →∞ 2C 2 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.

D BACKGROUND ON STOCHASTIC APPROXIMATION:

We first present a fundamental result for stochastic approximation which is obtained from Borkar (2008) . Consider a sequence of iterations in R d x t+1 = x t + γ t • [G(x t ) + M t+1 ], t ≥ 0, x 0 ∈ R d .

(D.1)

Here G : R d → R d is a deterministic mapping, M t+1 ∈ R d 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 : R d → R d is Lipschitz continuous.

• The stepsizes {γ t } t≥0 satisfies t≥0 γ t = ∞ and t≥0 γ 2 t < ∞;

• Random vectors {M t } t≥0 is a martingale difference sequence. That is, M 0 = 0, E[M t+1 | x τ , M τ , τ ≤ t] = 0. Moreover, we assume that there exists some

K > 0 such that E M t+1 2 | x τ , M τ , τ ≤ t ≤ K • (1 + x t 2 ).

Then the asymptotic behavior of the {x t } t≥0 in (D. 

:



Figures and Tables:

Figure1: Training Acrobot and MountainCar using online Q-learning. Here we set β t = 10 -3 for both problems. In addition, for Acrobot, we let α t be one of {10 -2 , 8 • 10 -3 , 3 • 10 -4 , 10 -4 }. For or MountainCar we set α t to be one of {0.7, 0.5, 5 • 10 -4 , 10 -4 }.

Figure 2: Training Pong and Breakout using two timescale actor-critic algorithm, where we use 32 agents, minibatch of size 20, with a fixed actor network stepsize α t ≡ 10 -4 , but a varied critic network stepsize β t ∈ {10 -7 , 2 • 10 -7 , 5 • 10 -4 , 10 -3 }. Left: training Pong. Right: training Breakout.

has a unique globally asymptotically stable equilibrium x * , we then have the following two theorems. Theorem D.2. Under Assumption D.1, if sup t x t 2 < ∞ almost surely, we havex t → x * almost surely. Theorem D.3. Under Assumption D.1, suppose lim c→∞ G(cx) c = G ∞ (x)exists uniformly on compact sets for someG ∞ ∈ C(R n ). If the ODE ẏ = G ∞ (y) has origin as the unique globally asymptotically stable equilibrium, then we have sup t x t < ∞ almost surely.

stepsizes {α t , β t } t≥0 . 2: Output: The sequences {θ t } t≥0 and {ω t } t≥0 . 3: for t = 0, 1, 2, . . . do Sample (s t , a t ) ∼ ρ, observe reward R(s t , a t ) and next state s t .

Table content: <table><tr><td>4:</td></tr></table>

The actor-critic algorithm with nonlinear function approximation. Initialization ω 0 ∈ R d and θ 0 ∈ R p , stepsizes {α t , β t } t≥0 . 2: Output: The sequences {θ t } t≥0 and {ω t } t≥0 .

Table content: <table><tr><td>1)</td></tr><tr><td>7: end for</td></tr><tr><td>Algorithm 3</td></tr></table>

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)| ≤ V max and ∇ ω log π ω (a | s) 2 ≤ π max . Thus δ t and A t defined in (C.10) satisfy |δ t | ≤ 2V max and A

Table content: <table/>

ϑ(ω t )] + α t • ψ 2G max • π max for any θ (1) , θ (2) ∈ R d and any ω ∈ Ω. Then, by Cauchy-Schwarz inequality, we haveψ (2) t 2 ≤ E h(θ t , ω t ) -h[ϑ(ω t ), ω t ] 2 F ≤ 2G max • π max • E θ t -ϑ(ω t ) 2 F

Table content: <table><tr><td>where ϑ(ω  (2) t</td><td>(1)</td><td>(2) t</td><td>,</td><td>(C.14) (2) t</td></tr></table>

Peer review (iclr2019):
 The authors frame value function estimation and policy learning as bilevel optimization problems, then present a two-timescale stochastic optimization algorithm and convergence results with non-linear function approximators. Finally, they relate the use of target networks in DQN to their two-timescale procedure. The authors claim that their first contribution is to "unify the problems of value function estimation and policy learning using the framework of bilevel optimization." The bilevel viewpoint has a long history in the RL literature. Are the authors claiming novelty here? If so, can they clarify which parts are novel? The paper is missing important previous work, SBEED (Dai et al. 2018) which shows (seemingly much stronger) convergence results for a smoothed RL problem. The authors need to compare their approach against SBEED and clearly explain what more they are bringing. Furthermore, the Fenchel trick used in SBEED could also be used to attack the "double sampling" issue here, resulting in a saddle-point problem (which is more specific than the bilevel problem). Does going to the bilevel perspective buy us anything? ===== In response to the author*s comments, I have increased my score. The practical implications of this theoretical work are unclear. It*s nice that it relates to DQN, but it does not provide additional insight into how to improve existing approaches. The authors could significantly strengthen the paper by expanding in this area.