Year: 2021

Abstract:
A simple and natural algorithm for reinforcement learning (RL) is Monte Carlo Exploring Starts (MCES), where the Q-function is estimated by averaging the Monte Carlo returns, and the policy is improved by choosing actions that maximize the current estimate of the Q-function. Exploration is performed by “exploring starts”, that is, each episode begins with a randomly chosen state and action, and then follows the current policy to the terminal state. In the classic book on RL by Sutton & Barto (2018), it is stated that establishing convergence for the MCES algorithm is one of the most important remaining open theoretical problems in RL. However, the convergence question for MCES turns out to be quite nuanced. Bertsekas & Tsitsiklis (1996) provide a counter-example showing that the MCES algorithm does not necessarily converge. Tsitsiklis (2002) further shows that if the original MCES algorithm is modified so that the Q-function estimates are updated at the same rate for all state-action pairs, and the discount factor is strictly less than one, then the MCES algorithm converges. In this paper we make headway with the original and more efficient MCES algorithm given in Sutton & Barto (1998), establishing almost sure convergence for Optimal Policy Feed-Forward MDPs, which are MDPs whose states are not revisited within any episode when using an optimal policy. Such MDPs include a large class of environments such as all deterministic environments and all episodic environments with a timestep or any monotonically changing values as part of the state. Different from the previous proofs using stochastic approximations, we introduce a novel inductive approach, which is very simple and only makes use of the strong law of large numbers.

heading: 1 INTRODUCTION
text: Perhaps the most famous algorithm in tabular reinforcement learning is the so-called Q-learning algorithm. Under very general conditions, it is well known that the Q-learning converges to the optimal Q-function with probability one (Tsitsiklis, 1994; Jaakkola et al., 1994). Importantly, in order to guarantee convergence for Q-learning, it is only required that every state-action pair be visited infinitely often. Furthermore, as discussed in the related work, Q-learning converges for the infinite-horizon discounted problem as well as for the non-discounted terminal-state problem (also known as the stochastic shortest-path problem).
The Q-learning algorithm is inspired by dynamic programming and uses back-ups to update the estimates of the optimal Q-function. An alternative methodological approach, which does not use back-ups, is to use the Monte Carlo episodic returns to estimate the values of the Q-function. In order for such an algorithm to succeed at finding an optimal policy, the algorithm must include some form of exploration. A simple form of exploration is “exploring starts,” where at the beginning of each episode, a random state-action pair is chosen. In the classic book on reinforcement learning by Sutton & Barto (2018), the authors describe such an algorithm, namely, Monte Carlo Exploring Starts (MCES). In the MCES algorithm, after a (random-length) episode, the Q-function estimate is updated with the Monte Carlo return for each state-action pair along the episode, and the policy is improved in the usual fashion by setting it to the argmax of the current Q-function estimate. Exploration is performed by exploring starts, where the initial state-action pairs may be chosen with any distribution.
We briefly remark here that AlphaZero is a Monte Carlo algorithm in that it runs episodes to completion and uses the returns from those episodes for the targets in the loss function (Silver et al., 2018). AlphaZero additionally uses function approximators (convolutional networks) and planning (Monte Carlo Tree Search), and is thus much more complicated than MCES. But AlphaZero is nonetheless fundamentally a Monte Carlo algorithm rather than a Q-learning-based algorithm. We mention AlphaZero here in order to emphasize that Monte Carlo algorithms are indeed used in practice, and it is therefore important to gain a deep understanding of their underlying theoretical properties.
Since Q-learning converges under very general conditions, a natural question is: does MCES converge under equally general conditions? In the 1996 book, Bertsekas & Tsitsiklis (1996) provide a counter-example showing that the MCES algorithm does not necessarily converge. See also Liu (2020) for numerical results in this direction. Thus, we see that the MCES convergence problem is fundamentally trickier than the Q-learning convergence problem. Instead of establishing a very general result as in Q-learning, we can at best establish convergence for a broad class of special-cases.
Sutton and Barto write at the end of Section 5.3: “In our opinion, this is one of the most fundamental open theoretical questions in reinforcement learning”. This paper is focused on this fundamental question. Although other questions, such as rates of convergence and regret bounds, are also important, in this paper our goal is to address the fundamental question of convergence.
Tsitsiklis (2002) made significant progress with the MCES convergence problem, showing that almost sure convergence is guaranteed if the following three conditions hold: (i) the discount factor is strictly less than one; (ii) the MCES algorithm is modified so that after an episode, the Q-function estimate is updated with the Monte Carlo return only for the initial state-action pair of the episode; and (iii) the algorithm is further modified so that the initial state-action pair in an episode is chosen with a uniform distribution. As in the proof of Q-learning, Tsitsiklis’s proof is based on stochastic approximations. The conditions (ii) and (iii) combined ensure that the Q function estimates are updated at the same average rate for all state-action pairs, and both conditions appear to be crucial for establishing convergence in the proof in Tsitsiklis (2002). However, these two conditions have the following drawbacks:
• Perhaps most importantly, condition (ii) results in a substantially less efficient algorithm, since only one Q-function value is updated per episode. The original Sutton and Barto version is more efficient since after each episode, many Q-values are typically updated rather than just one. (We also note as an aside that AlphaZero will also collect and use Monte Carlo return for all states along the episode, not just for the first state in the episode, as discussed on page 2 of Silver et al. (2017))
• Similar to the idea of importance sampling, one may want to use a non-uniform distribution for the starting state-action pairs to accelerate convergence.
• In some cases, we may not have access to a simulator to generate uniform exploring starts. Instead, we may run episodes by interacting directly with the real environment. Such natural interactions may lead to starting from every state, but not uniformly. An example would be playing blackjack at a casino rather than training with a simulator.
In this paper we provide new convergence results and a new proof methodology for MCES. Unlike the result in Tsitsiklis (2002), the results reported here do not modify the original MCES algorithm and do not require any of the conditions (i) − (iii). Hence, our results do not have the three drawbacks listed above, and also allow for no discounting (as in the stochastic shortest path problem). However, our proofs require restrictions on the dynamics of the underlying MDP. Specifically, we require that under the optimal policy, a state is never revisited. This class of MDPs includes stochastic feed-forward environments such as Blackjack (Sutton & Barto, 2018) and also all deterministic MDPs, such as gridworlds (Sutton & Barto, 2018), Go and Chess (when played against a fixed opponent policy), and the MuJoCo environments (Todorov et al., 2012) (Episodic MuJoCo tasks fall into the category of OPFF MDPs because the MuJoCo simulation is deterministic). Moreover, if the trajectory horizon is instead fixed and deterministic, we show that the original MCES algorithm always converges (to a time-dependent) optimal policy, without any conditions on the dynamics, initial state-action distribution or the discount factor.
Importantly, we also provide a new proof methodology. Our proof is very simple, making use of only the Strong Law of Large Numbers (SLLN) and a simple inductive argument. The proof does
not use stochastic approximations, contraction mappings, or martingales, and can be done in an undergraduate course in machine learning. We believe that this new proof methodology provides new insights for episodic RL problems.
In addition to the theoretical results, we present numerical experiments that show the original MCES can be much more efficient than the modified MCES, further highlighting the importance of improving our understanding on the convergence properties of the original MCES algorithm.

heading: 2 RELATED WORK
text: Some authors refer to an MDP with a finite horizon H as an episodic MDP. For finite horizon MDPs, the optimal Q-function and optimal policy are in general non-stationary and depend on time. Here, following Sutton & Barto (2018), we instead reserve the term episodic MDPs for MDPs that terminate when the terminal state is reached, and thus the episode length is not fixed at H and may have a random length. Moreover, for such terminal-state episodic MDPs, under very general conditions, the optimal Q-function and policy are stationary and do not depend on time (as in infinitehorizon discounted MDPs). When the dynamics are known and the discount factor equals 1, the episodic optimization problem considered here is equivalent to the stochastic shortest path problem (SSPP) (see Bertsekas & Tsitsiklis (1991) and references therein; also see Chapter 2 of Bertsekas (2012)). Under very general conditions, value iteration converges to the optimal value function, from which an optimal stationary policy can be constructed.
Convergence theory for RL algorithms has a long history. For the infinite-horizon discounted criterion, by showing that Q-learning is a form of stochastic approximations, Tsitsiklis (1994) and Jaakkola et al. (1994) showed that Q-learning converges almost surely to the optimal Q-function under very general conditions. There are also convergence results for Q-learning applied to episodic MDPs as defined in this paper with discount factor equal to 1. Tsitsiklis [8, Theorems 2 and 4(c)] proved that if the sequence of Q-learning iterates is bounded, then Q-learning converges to the optimal Q values almost surely. Yu & Bertsekas (2013) prove that the sequence of Q-learning iterates is bounded for episodic MDPs with or without non-negativity assumptions, fully establishing the convergence of Q-learning for terminal-state episodic RL problems.
This paper is primarily concerned with the convergence of the MCES algorithm. In the Introduction we reviewed the important work of Sutton & Barto (1998), Bertsekas & Tsitsiklis (1996), and Tsitsiklis (2002). Importantly, unlike Q-learning, the MCES algorithm is not guaranteed to converge for all types of MDPs. Indeed, in Section 5.4 of Bertsekas & Tsitsiklis (1996), Example 5.12 shows that MCES is not guaranteed to converge for a continuing task MDP. However, if the algorithm is modified, as described in the Introduction, then convergence is guaranteed (Tsitsiklis, 2002). Recently, Chen (2018) extended the convergence result in Tsitsiklis (2002) to the undiscounted case, under the assumption that all policies are proper, that is, regardless of the initial state, all policies will lead to a terminal state in finite time with probability one. More recently, Liu (2020) relaxed the all policies being proper condition. As in Tsitsiklis (2002), both Chen (2018) and Liu (2020) assume conditions (ii)− (iii) stated in the introduction, and their proofs employ the stochastic approximations methodology in Tsitsiklis (1994). The results we develop here are complementary to the results in Tsitsiklis (2002), Chen (2018), and Liu (2020), in that they do not require the strong algorithmic assumptions (ii)− (iii) described in the Introduction, and they use an entirely different proof methodology.
In this work we focus on the question of convergence of the MCES problem. We briefly mention, there is also a large body of (mostly orthogonal) work on rates of convergence and regret analysis for Q-learning (e.g. see Jin et al. (2018)) and also for Monte Carlo approaches (e.g., see Kocsis & Szepesvári (2006) Azar et al. (2017)). To the best of our knowledge, these regret bounds assume finite-horizon MDPs (for which the optimal policy is time-dependent) rather than the terminal-state episodic MDPs considered here.

heading: 3 MDP FORMULATION
text: Following the notation of Sutton & Barto (2018), a finite Markov decision process is defined by a finite state space S and a finite action space A, reward function r(s, a) mapping S ×A to the reals,
and a dynamics function p(·|s, a), which for every s ∈ S and a ∈ A gives a probability distribution over the state space S. A (deterministic and stationary) policy π is a mapping from the state space S to the action space A. We denote π(s) for the action selected under policy π when in state s. Denote Sπt for the state at time t under policy π. Given any policy π, the state evolution becomes a well-defined Markov chain with transition probabilities
P (Sπt+1 = s ′|Sπt = s) = p(s′|s, π(s))

heading: 3.1 RETURN FOR RANDOM-LENGTH EPISODES
text: As indicated in Chapters 4 and 5 of Sutton & Barto (2018), for RL algorithms based on Monte Carlo methods, we assume that the task is episodic, that is “experience is divided into episodes, and all episodes eventually terminate no matter what actions are selected.” Examples of episodic tasks include “plays of a game, trips through a maze, or any sort of repeated interaction”. Chapter 4 of Sutton & Barto (2018) further states: “Each episode ends in a special state called the terminal state, followed by a reset to a standard starting state or to a sample from a standard distribution of starting states”.
The “Cliff Walking” example in Sutton & Barto (2018) is an example of an “episodic MDP”. Here the terminal state is the union of the goal state and the cliff state. Although the terminal state will not be reached by all policies due to possible cycling, it will clearly be reached by the optimal policy. Another example of an episodic MDP, discussed at length in Sutton and Barto, is “Blackjack”. Here we can create a terminal state which is entered whenever the player sticks or goes bust. For Blackjack, the terminal state will be reached by all policies. Let s̃ denote the terminal state. (If there are multiple terminal states, without loss in generality they can be lumped into one state.)
When using policy π to generate an episode, let
Tπ = min{ t : Sπt = s̃} (1)
be the time when the episode ends. The expected total reward when starting in state s is
vπ(s) = E[ Tπ∑ t=0 r(Sπt , π(S π t ))|Sπ0 = s] (2)
Maximizing (2) corresponds to the stochastic shortest path problem (as defined in Bertsekas & Tsitsiklis (1991); Bertsekas (2012)), for which there exists an optimal policy that is both stationary and deterministic (for example, see Proposition 2.2 of Bertsekas (2012)).
At the end of this paper we will also consider the finite horizon problem of maximizing:
vHπ (s) = E[ H∑ t=0 r(Sπt , π(S π t , t))|Sπ0 = s] (3)
where H is a fixed and given horizon. For this criterion, it is well-known that optimal policy π(s) = (π(s, 1), . . . , π(s,H)) is non-stationary. For the finite-horizon problem, it is not required that the MDP have a terminal state.

heading: 3.2 CLASSES OF MDPS
text: We will prove convergence results for important classes of MDPs. For any MDP, define the MDP graph as follows: the nodes of the graph are the MDP states; there is a directed link from state s to s′ if there exists an action a such that p(s′|s, a) > 0. We say an environment is Stochastic Feed-Forward (SFF) if a state cannot be revisited within any episode. More precisely, the MDP is SFF if its MDP graph has no cycles. Note that transitions are permitted to be stochastic. SFF environments occur naturally in practice. For example, the Blackjack environment, studied in detail in Sutton & Barto (2018), is SFF. We say an environment is Optimal Policy Feed-Forward (OPFF) if under any optimal policy a state is never re-visited. More precisely, construct a sub-graph of the MDP graph as follows: each state s is a node in the
graph, and there is a directed edge from node s to s′ if p(s′|s, a∗) > 0 for some optimal action a∗. The MDP is OPFF if this sub-graph is acyclic.
An environment is said to be a deterministic environment if for any state s and chosen action a, the reward and subsequent state s′ are given by two (unknown) deterministic functions r = r(s, a) and s′ = g(s, a). Many natural environments are deterministic. For example, in Sutton & Barto (2018), environments Tic-Tac-Toe, Gridworld, Golf, Windy Gridworld, and Cliff Walking are all deterministic. Moreover, many natural environments with continuous state and action spaces are deterministic, such as the Mujoco robotic locomotion environments (Todorov et al., 2012).
It is easily seen that all SFF MDPs are OPFF, and all deterministic MDPs for which the optimal policy terminates w.p.1 are OPFF.

heading: 4 MONTE CARLO WITH EXPLORING STARTS
text: The MCES algorithm is given in Algorithm 1. The MCES algorithm is a very natural and simple algorithm, which uses only Monte Carlo returns and no backups for updating the Q-function and training the policy. A natural question is: does it converge to the optimal policy? As mentioned in the Introduction, unlike for Q-learning, it does not converge for general MDPs. We instead establish convergence for important classes of MDPs.
Algorithm 1 is consistent with the MCES algorithm in Sutton & Barto (2018) and has the following important features:
• Q(St, At) is updated for every St, At pair along the episode, and not just for S0, A0 as required in (Tsitsiklis, 2002).
• The initial state and action in an episode can be chosen arbitrarily (but infinitely often), and does not have to be chosen according to a uniform distribution as required in (Tsitsiklis, 2002).
• For simplicity, we present the algorithm with no discounting (i.e., γ = 1). However, the subsequent proofs go through for any discount factor γ ≤ 1. (The proof in Tsitsiklis (2002) requires γ < 1.)
We emphasize that although the results in Tsitsiklis (2002) require restrictive assumptions on the algorithm, the results in Tsitsiklis (2002) hold for general MDPs. Our results do not make restrictive algorithmic assumptions, but only hold for a sub-class of MDPs.
Algorithm 1 MCES 1: Initialize: π(s) ∈ A, Q(s, a) ∈ R, for all s ∈ S, a ∈ A, arbitrarily; Returns(s, a)← empty list, for all s ∈ S, a ∈ A.
2: while True do 3: Choose S0 ∈ S, A0 ∈ A s.t. all pairs are chosen infinitely often. 4: Generate an episode following π: S0, A0, S1, A1, . . . , ST−1, AT−1, ST . 5: G← 0 6: for t = T − 1, T − 2, . . . , 0 do 7: G← G+ r(St, At) 8: Append G to Returns(St, At) 9: Q(St, At)← average(Returns(St, At))
10: π(St)← arg maxaQ(St, a)
We begin with the following lemma, whose proof can be found in Appendix A. Lemma 1. Let X1, X2, . . . be a sequence of random variables. Let T be a random variable taking values in the positive integers, and suppose P (T <∞) = 1. Suppose that for every positive integer n, Xn, Xn+1, . . . are i.i.d. with finite mean x∗ and finite variance when conditioned on T = n. Then P (limN→∞ 1N ∑N i=1Xi = x ∗) = 1.
Say that the MCES algorithm begins iteration u at the uth time that an episode runs, and ends the iteration after Q and π have been updated (basically an iteration in the while loop in Algorithm 1).
Denote by Qu(s, a) and πu(s) for the values of Q(s, a) and π(s) at the end of the uth iteration. For simplicity, assume that the MDP has a unique optimal policy π∗, and denote q∗(s, a) for the corresponding action-value function. Note that the proof extends easily to the case of multiple optimal policies.
We now state and prove the convergence result for SFF MDPs. We provide the full proof here in order to highlight how simple it is. Afterwards we will state the more general result for OPFF MDPs, for which the proof is a little more complicated, Theorem 1. Suppose the MDP is SFF. Then Qu(s, a) converges to q∗(s, a) and πu(s) converges to π∗(s) for all s ∈ S and all a ∈ A w.p.1.
Proof. Because the MDP is SFF, its MDP graph is a Directed Acyclic Graph (DAG). So we can re-order the N states such that from state sk and selecting any action, we can only transition to a state in {sk+1, . . . , sN}. Note state sN is the terminal state, and note that from state sN−1 all actions lead to sN .
The proof is by backward induction. The result is trivially true for s = sN . Suppose it is true for all states in {sk+1, . . . , sN} and all actions a ∈ A. We now show it is true for sk and all actions a ∈ A. We first establish Qu(sk, a) converges to q∗(sk, a) for all a ∈ A w.p.1. Let T be the iteration u when πu(s) has converged to π∗(s) for all s ∈ {sk+1, . . . , sN}. By the inductive assumption, P (T <∞) = 1. Let a ∈ A be any action. Now consider any episode after time T in which we visit state sk and choose action a. Because the MDP is SFF, the next state will be in {sk+1, . . . , sN}, and because of the inductive assumption, the subsequent actions in the episode will follow the optimal policy π∗ until the episode terminates. By the definition of q∗(sk, a), the expected return for such an episode is equal to q∗(sk, a). Let Gn denote the return for (sk, a) for the nth episode in which (sk, a) appears. Note that after time T , these returns are i.i.d. with mean q∗(sk, a). Therefore, by Lemma 1,
lim u→∞ Qu(sk, a) = lim N→∞
1
N N∑ n=1 Gn = q ∗(sk, a) w.p.1 (4)
It remains to show that πu(sk) converges to π∗(sk) w.p.1. Define a∗ = π∗(sk). Since π∗ is the unique optimal policy, we have:
q∗(sk, a ∗) ≥ q∗(sk, a) + ′ (5)
for some ′ > 0 for all a 6= a∗. Let Ω be the underlying sample space, and let Λ be the set of all ω ∈ Ω such that Qu(sk, a)(ω) converges to q∗(sk, a) for all a ∈ A. By (4), P (Λ) = 1. Thus for any ω ∈ Λ and any > 0, there exists a u′ (depending on ω) such that u ≥ u′ implies |q∗(sk, a)−Qu(sk, a)(ω)| ≤ for all a ∈ A (6) Let be any number satisfying 0 < < ′/2, let ω ∈ Λ, and u′ be such that (6) is satisfied for all u ≥ u′. It follows from (5) and (6) that for any u ≥ u′ we have
Qu(sk, a ∗)(ω) ≥ q∗(sk, a∗)− (7)
≥ q∗(sk, a) + ′ − (8) ≥ Qu(sk, a)(ω) + ′ − 2 (9) > Qu(sk, a)(ω) (10)
for all a 6= a∗. Let u be any iteration after u′ such that state sk is visited in the corresponding episode. From the MCES algorithm, πu(sk)(ω) = arg maxaQu(sk, a)(ω). Thus the above inequality implies πu(sk)(ω) = a∗; furthermore, πu(sk)(ω) will be unchanged in any subsequent iteration. Thus, for every ω ∈ Λ, πu(sk)(ω) converges to a∗. Since P (Λ) = 1, it follows πu(sk) converges to a∗ w.p.1., completing the proof.
We make the following additional observations: (1) It is not necessary to assume the MDP has a unique optimal policy. The theorem statement and proof go through with minor modification without this assumption. (2) Also we can allow for random reward, with distribution depending on the current state and action. The proof goes through with minor changes.

heading: 5 OPFF MDPS
text: For the case of OPFF, we first need to modify the algorithm slightly to address the issue that an episode might never reach the terminal state for some policies (for example, due to cycling). To this end, let M be some upper bound on the number of states in our MDP. We assume that the algorithm designer has access to such an upper bound (which may be very loose). We modify the algorithm so that if an episode does not terminate within M steps, the episode will be forced to terminate and the returns will simply not be used. We also initialize all Q values to be −∞, so that the policy will always prefer an action that has led to at least one valid return over actions that never yield a valid return. The modified algorithm is given in Algorithm 2. Finally, as in Sutton & Barto (2018), we use first-visit returns for calculating the average return. (This mechanism is not needed for SFF MDPs since under all policies states are never revisited.)
Algorithm 2 First-visit MCES for OPFF MDPs 1: Initialize: π(s) ∈ A, Q(s, a) = −∞, for all s ∈ S, a ∈ A, arbitrarily; Returns(s, a)← empty list, for all s ∈ S, a ∈ A.
2: while True do 3: Choose S0 ∈ S, A0 ∈ A s.t. all pairs are chosen infinitely often. 4: Generate an episode following π: S0, A0, S1, A1, . . . , ST−1, AT−1, ST . 5: if the episode does not end in less than M time steps then 6: terminate the episode at time step M 7: else 8: G← 0 9: for t = T − 1, T − 2, . . . , 0 do
10: G← G+ r(St, At) 11: if St, At does not appears in S0, A0, S1, A1 . . . , St−1, At−1 then 12: Append G to Returns(St, At) 13: Q(St, At)← average(Returns(St, At)) 14: π(St)← arg maxaQ(St, a)
Theorem 2. Suppose the MDP is OPFF. Then Qu(s, a) converges to q∗(s, a) and πu(s) converges to π∗(s) for all s ∈ S and all a ∈ A w.p.1.
The proof can be found in the appendix. As with SFF MDPs, it is not necessary to assume that the MDP has a unique optimal policy; furthermore, the reward can be random (with distribution depending on current state and action). Note for OPFF MDPs, our proof has to take a more sophisticated approach since we now can transition to arbitrary state by taking any non-optimal action.

heading: 6 FINITE-HORIZON MDPS
text: In this section, we extend our results to finite-horizon MDPs. In this case, we will be able to establish convergence for all MDPs (i.e., not just for OPFF MDPs).
A finite-horizon MDP is defined by a finite horizon set H = {0, 1, . . . ,H}, a finite state space S, a finite action space A, a reward function r(s, t, a) mapping S ×H ×A to the reals, and a dynamics function p(·|s, t, a), which for every s ∈ S, a ∈ A and time step t, gives a probability distribution over the state space S. The horizon H is the fixed time at which the episode terminates. Note in this setting, the optimal policy π∗(s, t) will also be time-dependent, even if p(·|s, t, a) and r(s, t, a) do not depend on t.
The MCES algorithm for this setting is given in Algorithm 3. Note that in this version of the algorithm, during exploring starts we need to choose an S0 ∈ S, A0 ∈ A, and an h ∈ [0, H],. Corollary 1. Suppose we are using the finite-horizon optimization criterion. Then Qu(s, t, a) converges to q∗(s, t, a) and πu(s, t) converges to π∗(s, t) for all s ∈ S, t ∈ H and all a ∈ A w.p.1.
Proof. A finite-horizon MDP is equivalent to a standard MDP where the time step is treated as part of the state. Since the number of time steps monotonically increases, this MDP is SFF. Thus the convergence of MCES for the finite-horizon MDP setting follows directly from Theorem 1.
Algorithm 3 MCES for Finite-Horizon MDPs 1: Initialize: π(s, t) ∈ A, Q(s, t, a) ∈ R, for all s ∈ S, t ∈ [0, H], a ∈ A, arbitrarily; Returns(s, t, a)← empty list, for all s ∈ S, t ∈ [0, H], a ∈ A.
2: while True do 3: Choose S0 ∈ S, A0 ∈ A, h ∈ [0, H], s.t. all triples are chosen infinitely often. 4: Generate an episode following π: Sh, Ah, Sh+1, Ah+1, . . . , SH−1, AH−1, SH . 5: G← 0 6: for t = H − 1, H − 2, . . . , h do 7: G← G+ r(St, t, At) 8: Append G to Returns(St, t, At) 9: Q(St, t, At)← average(Returns(St, t, At))
10: π(St, t)← arg maxaQ(St, t, a)

heading: 7 EXPERIMENTAL RESULTS
text: In addition to the theoretical results, we also provide experimental results to compare the convergence rate of the original MCES algorithm and the modified MCES algorithm in Tsitsiklis (2002), where the Q-function estimate is updated with Monte Carlo return only for the initial state-action pair of each episode. We will call the original MCES the “multi-update” variant, and the modified MCES the “first-update” variant. We consider two classical environments: blackjack and stochastic cliffwalking. We will briefly discuss the settings and summarize the results. A more detailed discussion is provided in the appendix.
For blackjack, we use the same problem setting as discussed in Sutton & Barto (1998). Blackjack is an episodic task where for each episode, the player is given 2 initial cards, and can request more cards (hits) or stops (sticks). The goal is to obtain cards whose numerical values sum to a number as great as possible without exceeding 21. Along with the two MCES variants, we also compare two initialization schemes: standard-init, where we initialize by first drawing two random cards from a deck of 52 cards; and uniform-init, where the initial state for an episode is uniformly sampled from the state space. We now compare their rate of convergence in terms of performance and the absolute Q update error, averaged across state-action pairs visited in each episode. Figure 1 shows uniform initialization converges faster than standard initialization, and the multi-update variant is faster than the first-update variant for both initialization schemes.
In cliff walking, an agent starts from the bottom left corner of a gridworld, and tries to move to the bottom right corner, without falling into a cliff (an area covering the bottom row of the gridworld). The agent gets a -1 reward for each step it takes, and a -100 for falling into the cliff. We consider two variants: SFF cliff walking and OPFF cliff walking tasks. For the SFF variant, the current time step of the episode is part of the state, so the MDP is a SFF MDP, and the agent tries to learn a time-dependent optimal policy. In this setting we add more stochasticity by having wind move the agent towards one of four directions with some probability. For the OPFF variant, the time step is not part of the state, and the wind only affect the agent when the agent moves to the right, and can only blow the agent one step upwards or downwards, making an OPFF MDP. We now compare the
convergence rate of the two MCES variants on these two cliff walking environments. We measure the convergence rate in terms of the performance and the average L1 distance between the current Q estimate and the optimal Q values. The results are summarized in Figure 2, the training curves are averaged across a number of different gridworld sizes and wind probabilities. Results show that multi-update MCES consistently learns faster than first-update MCES.
Our experimental results show that the multi-update MCES converges much faster than the firstupdate MCES. These results further emphasize the importance of gaining a better understanding of the convergence properties of the original multi-update MCES variant, which is much more efficient.

heading: 8 CONCLUSION
text: Theorem 2 of this paper shows that as long as the episodic MDP is OPFF, then the MCES algorithm converges to the optimal policy. As discussed in Section 3.2, many environments of practical interest are OPFF. Our proof does not require that the Q-values be updated at the same rate for all state-action pairs, thereby allowing more flexibility in the algorithm design. Our proof methodology is also novel, and can potentially be applied to other classes of RL problems. Moreover, our methodology also allows us to establish convergence results for finite-horizon MDPs as a simple corollary of Theorem 2. Combining the results of Bertsekas & Tsitsiklis (1996), Tsitsiklis (2002), Chen (2018), Liu (2020), and the results here gives Figure 3, which summarizes what is now known about convergence of the MCES algorithm.
The results in this paper along with other previous works (Tsitsiklis, 2002; Chen, 2018; Liu, 2020) make significant progress in establishing the convergence of the MCES algorithm. Many cases of practical interest are covered by the conditions in these papers. It still remains an open problem whether there exist conditions on MDPs that are weaker than the OPFF, and can still guarantee the convergence of the original MCES algorithm.

heading: A PROOF OF LEMMA 1
text: Proof. We have
P ( lim N→∞
1
N N∑ i=1 Xi = x ∗)
= ∞∑ n=1 P ( lim N→∞ 1 N N∑ i=1 Xi = x ∗|T = n)P (T = n)
= ∞∑ n=1 P ( lim N→∞ ( 1 N n−1∑ i=1 Xi + 1 N N∑ i=n Xi) = x ∗|T = n)P (T = n)
= ∞∑ n=1 P ( lim N→∞ 1 N N∑ i=n Xi = x ∗|T = n)P (T = n) = 1
The first equality follows from P (T <∞) = 1. The last equality follows from the conditional i.i.d. assumption and the Strong Law of Large Numbers. Note we can apply the Strong Law of Large Numbers here because as stated in Lemma 1, we have the assumption that Xn, Xn+1, . . . are i.i.d. with finite mean and finite variance.

heading: B PROOF OF THEOREM 2
text: Proof. Because the MDP is OPFF, its optimal policy MDP graph is a DAG, so we can re-order the states such that from state sk and selecting the optimal action a∗k, we can only transition to a state in {sk+1, . . . , sN}. Note that state sN is the terminal state, and note that from state sN−1 the optimal action only leads to sN .
We first show that for all k = 1, . . . , N , Qu(sk, a∗k) converges to q ∗(sk, a ∗ k) and that πu(sk) converges to π∗(sk), w.p.1. Once we establish this convergence result for all k = 1, . . . , N , we will then complete the proof by establishing convergence of Qu(sk, a) for arbitrary actions a. Note that the organization of this proof is slightly more complicated than that of Theorem 1 due to the weaker OPFF assumption.
The result is trivially true for s = sN . Suppose now Qu(sj , a∗j ) converges to q ∗(sj , a ∗ j ) and that πu(sj) converges to π∗(sj), w.p.1 for all j = k+ 1, . . . , N . We now show Qu(sk, a∗k) converges to q∗(sk, a ∗ k) and that πu(sk) converges to π ∗(sk), w.p.1. Denote a∗ = a∗k.
Let T be the iteration u when πu(s) has converged to π∗u(s) for all s ∈ {sk+1, . . . , sN}. By the inductive assumption, P (T < ∞) = 1. Now consider any episode after time T that for some timestep in this episode, we arrive in state sk and chooses the optimal action a∗. Because the MDP is OPFF, the next state will be in {sk+1, . . . , sN}, and because of the inductive assumption the subsequent actions in the episode will follow the optimal policy π∗ until the episode terminates within a finite number of steps. By the definition of q∗(sk, a∗), the expected return for (sk, a∗) in this episode is equal to q∗(sk, a∗). Let Gn denote the return for nth episode in which we visit sk and chooses optimal action a∗. Note that after time T , these returns are i.i.d. with mean q∗(sk, a∗). Therefore, by Lemma 1,
lim u→∞
Qu(sk, a ∗) = lim
N→∞
1
N N∑ n=1 Gn = q ∗(sk, a ∗) w.p.1 (11)
Next we show that πu(sk) converges to π∗(sk) = a∗ w.p.1. Since π∗ is the unique optimal policy, we have:
q∗(sk, a ∗) ≥ q∗(sk, a) + ′ (12)
for some ′ > 0 for all a 6= a∗. The proof at this stage is different from the proof at the corresponding stage in the proof of Theorem 1 since we can now only use (11) for a = a∗.
Consider state sk and an arbitrary action a ∈ A. From the MCES algorithm, we have Qu(sk, a) = 1 Lu ∑Lu l=1Gl, where Lu is the total number of first-visit returns used to compute Qu(sk, a) up through the uth iteration, and Gl is the return value for the lth such iteration. Let Π denote the (finite) set of all deterministic policies, Lπu denote the number of first-visit returns used to compute Qu(sk, a) up through the uth iteration when using policy π, and Gπl , 1 ≤ l ≤ Lπu, denote the lth return value when policy π is used. We have
Qu(sk, a) = 1
Lu Lu∑ l=1 Gl (13)
= ∑ π∈Π Lπu Lu ( 1 Lπu Lπu∑ l=1 Gπl ) (14)
By the law of large numbers, we know that for any policy π such that Lπu →∞ we have w.p.1
lim u→∞
1
Lπu Lπu∑ l=1 Gπl = q π(sk, a) ≤ q∗(sk, a) (15)
where qπ(sk, a) is the action-value function for policy π. The inequality in (15) follows from the definition of q∗(s, a). It follows from (14) and (15) that w.p.1
lim sup u→∞
Qu(sk, a) ≤ q∗(sk, a) for all a (16)
Note that in the OPFF setting, in the special case that no valid return has been obtained for (sk, a), then Qu(sk, a) = −∞ ≤ q∗(sk, a), so the above inequality still holds. Let Ω be the underlying sample space, and let Λ ⊂ Ω be the set over which (16) holds. Note that P (Λ) = 1. Thus for any ω ∈ Λ and any > 0, there exists a u′ such that u ≥ u′ implies
Qu(sk, a)(ω) ≤ q∗(sk, a) + for all a ∈ A (17)
Let be any number satisfying 0 < < ′/2, let ω ∈ Λ, and u′ be such that (17) is satisfied for all u ≥ u′. It follows from (11), (12) and (17) that for any u ≥ u′ we have
Qu(sk, a ∗)(ω) ≥ q∗(sk, a∗)− (18)
≥ q∗(sk, a) + ′ − (19) ≥ Qu(sk, a)(ω) + ′ − 2 (20) > Qu(sk, a)(ω) (21)
for all a 6= a∗. Let u be any iteration after u′ such that the episode includes state sk. From the MCES algorithm, πu(sk)(ω) = arg maxaQu(sk, a)(ω). Thus the above inequality implies πu(sk)(ω) = a
∗; furthermore, πu(sk)(ω) will be unchanged in any subsequent iteration. Thus, for every ω ∈ Λ, πu(sk)(ω) converges to a∗. Since P (Λ) = 1, it follows πu(sk) converges to a∗ w.p.1. We have now shown that for all k = 1, . . . , N , Qu(sk, a∗k) converges to q ∗(sk, a ∗ k) and that πu(sk) converges to π∗(sk), w.p.1. It remains to show convergence of Qu(s, a) to q∗(s, a) for arbitrary state s and action a. Let u′ be such that u ≥ u′, πu(s) = π∗(s) for all s ∈ S. Consider an episode after iteration u′ in which we visit state s and take action a. After taking action a, the policy follows the optimal policy π∗. Thus the expected return for (s, a) in this episode is q∗(s, a). We can thus once again apply Lemma 1 to show Qu(s, a) converges to q∗(s, a) w.p.1, thereby completing the proof.

heading: C ADDITIONAL EXPERIMENTAL DETAILS
text: C.1 BLACKJACK ENVIRONMENT
Here we give a more in-depth discussion on our blackjack experiments.
We use the same problem setting as discussed in Sutton & Barto (1998). We consider only a single player against a dealer. The goal of the blackjack game is to request a number of cards so that the sum of the numerical values of your cards is as great as possible without exceeding 21. All face cards will be counted as 10 and an ace can be counted as either 1 or 11. If the player holds an ace that can be counted as 11 without causing the total value to exceed 21, then the ace is said to be usable.
For each round of blackjack, both the player and the dealer will get two cards respectively at the beginning. One of the dealer’s cards is face up and another is face down. For each time step in the episode, the player has two possible actions: either to request an additional card (hits), or stops (sticks), if the player’s sum exceeds 21 (goes bust), then the player loses. After the player sticks, The dealer will hit or stick according to a fixed policy: he sticks on any sum of 17 or greater and hits otherwise, if the dealer goes bust then the player wins. In the end, if both sides do not go bust, their sums are compared, and the player wins if the player’s sum is greater, and loses if the dealer’s sum is greater, and the game is a draw if both sides have the same sum. When the episode terminates, the reward is 1 if the player wins, -1 if the player loses, and 0 if the game is a draw. Note that in an episode, the player cannot revisit a previously visited state (if the player has a usable ace, the player can move into a state with a unusable ace, but not vice-versa). Therefore blackjack is a stochastic feed-forward (SFF) environment.
For blackjack, the player’s state consists of three components: the player’s current sum, the card that the dealer is showing, and whether the player has a usable ace. There are some states where the optimal policy is trivial. For example, when the player has a very small sum, the player can always hit and the sum value will increase for sure without the danger of going bust. If we ignore such special states, then we have a total of 200 states that are interesting to the player (it is 200 states considering the player’s sum (12-21), dealer’s showing card (ace-10) and whether the player has a usable ace (Sutton & Barto, 1998)). For the uniform initialization scheme, the initial state of the player is uniformly sampled from these 200 states.
For the standard initialization, we instead simply follow the rules of blackjack. We randomly draw cards for the player and the dealer, each of these cards can be one of the 13 cards (ace-10, J, Q and K) with equal probability. (The cards are dealt from an infinite deck, i.e., with replacement. )
When we compare the convergence rate of the multi-update MCES and the first-update MCES, we use performance and the average absolute Q update error. The Q update error for a state-action pair is simply the difference between the Q values before and after a Q update. For each episode, the average absolute Q update error is averaged over all state-action pairs that are updated in this episode. In all figures, the solid curve shows the mean value over 5 seeds, and the shaded area indicates the confidence interval.
In Figure 1, we see that the first-update MCES variant (which only updates the Q value for the initial state-action pair in each episode) works in blackjack even when we sample according to the standard rule of blackjack and not uniformly. This might be due to fact that for blackjack, although the initial state distribution under standard initialization (where the player gets 2 random initial cards from the dealer) is not the same as uniform initialization, it still sufficiently covers the state space, so the agent is able to update its value estimates for all state-action pairs and gradually learn a good policy. However, this is not the case for cliffwalking, where if we initialize an episode according to the standard rule, then the initial state for the agent is always at the the bottom left corner of the gridworld, making it impossible to update the value function for other states. In many practical problems, we might not have access to an initial state distribution that sufficiently covers the entire state space, so it is very important to gain a better understanding of the convergence properties of the multi-update MCES variant.
C.2 STOCHASTIC CLIFF WALKING ENVIRONMENT
Here we give a more in-depth discussion on our cliff walking experiments.
As illustrated in Figure 4, in the cliff walking environment, the agent starts from the bottom left corner of a gridworld (marked with the letter S), and tries to move to the goal state at the bottom right corner (marked with the letter G), without falling into the cliff area (shaded area at the bottom row of the gridworld).
In our setting, the agent can move in four directions (right, up, left, down), and gets a -1 reward for each step it takes, a -100 for falling into the cliff, and a 0 for reaching the goal state. If the agent reaches the goal state or falls off the cliff, the episode will immediately terminate. If the agent moves out of the boundary of the gridworld, the agent will be “bounced” back and will not be able to go outside the boundaries.
Here we consider two variants of the cliffwalking environment: SFF cliff walking and OPFF cliff walking. For the SFF variant, the current time step of the episode is part of the state. Since the time step can only increase, the MDP is now a SFF MDP, and the agent tries to learn a time-dependent optimal policy. In this setting we add stochasticity by having wind move the agent one step towards one of the four directions with some probability. For example, when the wind probability is 50%, there is 12.5% chance that the agent will take an additional random step for each direction due to the wind. In Figure 4 this is illustrated with the arrows near the position P2. If the agent is in the SFF cliff walking environment and is currently at position P2, then if the agent moves one step upward (indicated by the solid arrow), there is some chance that the agent will also take an additional step towards one of the four directions, with equal probability (indicated by dashed arrows). Note that the agent’s state space now includes the x, y positions of the agent, as well as the current time step.
For the OPFF variant, the time step is not part of the state. To make sure the environment is OPFF, we only allow the wind to affect the agent when it moves to the right, and the wind can only blow the agent one step upwards, or downwards. This is shown in Figure 4 by the arrows near the position P1, if the agent is in the OPFF cliff walking environment and is current in position P1, then if the agent moves one step to the right, the wind has some probability of making it take an additional step upwards or downwards, with equal probability. In this setting, if the agent takes any action other than moving one step right, then it will not be affected. Under such a setting, if the agent is following an optimal policy, then in an episode it will never revisit a previously visited state, thus the MDP is OPFF.
Special care is required when running MCES in the OPFF environment, since it is possible the agent can run into infinite loops (e.g. keep bumping into the boundary), depending on the initial policy. One simple method to tackle this issue is to have an artificial time limit, and if during one episode the agent reaches this time limit, the episode is terminated and the agent receives a large, negative reward. This allows deterministic agents to train effectively in these OPFF environments.
C.2.1 CLIFF WALKING EXPERIMENTAL RESULTS
We use performance and the average L1 distance to the optimal Q value as metrics for the convergence rates of the multi-update and first-update MCES variants. Here the optimal Q values are computed using value iteration. The full experimental results are shown in Figures 5, 6, 7 and 8. We present results on gridworld sizes of 8× 6, 12× 9, 16× 12 and wind probability = 0.1, 0.3, 0.5. In Fig 5 and Fig 6, we consider the OPFF cliff walking environment, where time is not included in the state space and the wind only affects the action to the right.
In Fig 7 and Fig 8, we consider the SFF cliff walking environment, where the current time step is included as part of the state and the wind can affect the agent in all four directions.
Results in both cliff walking environments, and across all tested gridworld size and wind probability consistently show that multi-update MCES learns faster than first-update MCES. These results show there is indeed a significant performance difference between these two variants of the MCES algorithm. We also observe a general trend that the performance gap tends to increase when the state space becomes larger (a larger gridworld) and when we have more stochasticity in the environment (a higher wind probability). In Figure 6 and 8, each row shows performance for a gridworld size and each column shows a wind probability, if we go from the top left figure (figure (a)) to the bottom
right figure (figure (i)), we see that the performance gap tends to become bigger. This result shows that taking more updates to the value estimate can be important especially in complex tasks with more randomness.

Review summaries:
This paper studies Monte Carlo with exploration starts algorithm for solving the reinforcement learning problem. The writing is clear and I enjoyed reading this paper. As for the results, asymptotic convergence of the algorithm is established without needing strong assumptions in related literature. As pointed out by the authors, the result resolves an important open problem in RL. The proof is simple and intuitive. Numerical experiments corroborate theoretical findings.

The paper studies the convergence of Monte Carlo Exploring Starts (MCES), in which the Q-function is estimated by averaging Monte Carlo returns and the policy is defined as the greedy policy w.r.t. this Q-function. The authors provide a technically simple proof of the convergence under different assumptions on the underlying MDP: (i) stochastic feed-forward MDP (in which states cannot be re-visited in an episode); (ii) optimal policy feed-forward (in which under the optimal policy states are not re-visited); (iii) finite-horizon MDPs. Given these additional assumptions, the analysis relaxes other assumptions employed in previous convergence proofs. Finally, experimental results to validate the considered set of assumptions is provided.