On the Convergence of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning
Authors: Che Wang
Shuhan Yuan
Kai Shao
Keith W. Ross
Venue: ICLR 2022 Poster (2022)
Keywords: reinforcement learning
convergence of reinforcement learning algorithm
monte carlo exploring starts

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 et al. (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.

Published as a conference paper at ICLR 2022
ON THE CONVERGENCE OF THE MONTE CARLO Ex- PLORING STARTS ALGORITHM FOR REINFORCEMENT LEARNING
Che Wang!.2 1.2
Shuhan Yuan"
Kai Shao
Keith Ross
1 New York University Shanghai
2 New York University
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 maxi- mize the current estimate of the Q-function. Exploration is performed by "explor- ing starts", that is, each episode begins with a randomly chosen state and action, and then follows the current policy to the terminal state. the classic book on RL by|Sune (Suttonn& & 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 the same rate for all state-action pairs, and the discount factor 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 (998). establishing almost sure convergence for Optimal Policy Feed-Forward MDPs. which are MDPs whose states are not revisited within any episode when using 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.
INTRODUCTION
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 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 algorithm to succeed at finding optimal policy, the algorithm must include some form of exploration. A simple form exploration is "exploring starts." " where at the beginning of each episode, 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
*Correspondence Keith Ross centthwwoss@ny..dde.

---

Published as a conference paper at ICLR 2022
Starts (MCES). In MCES, after (random-lenn) -eeggth 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 Monte Carlo algorithm in that it runs episodes to comple- tion and uses the returns from those episodes for the targets in the loss function (Silver et al.) 2018)) AlphaZero additionally uses function approximators and planning (Monte Carlo Tree Search), and is thus much more complicated than MCES. But AlphaZero is nonetheless fundamentally Monte Carlo algorithm rather than Q-learning-bon 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. Additional discussion provided in Appendix C
algorithm. We mention AlphaZero here in order to
Since Q-learning converges under very general conditions, natural question is: does MCES con- verge under equally general conditions? In the 1996 book, [Bertsekas & Tsitsiklis (996) 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 gen- eral result in Q-learning, we can at best establish convergence for 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 fundamen- tal open theoretical questions in reinforcement learning". This paper is focused this fundamental question. Although other questions, such as rates of convergence and regret bounds, are also impor- tant, 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 al- most 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 (iti) 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 (it) 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, discussed on page Silver et al. (201)) also see discussion in Appendix.)
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 natu- ral interactions may lead to starting from every state, but not uniformly. An example would be playing blackjack casino rather than training with simulator.
In this paper we provide new convergence results and new proof methodology for MCES. Unlike the result in Tsitsikhs (2002), the results reported here do not modify the original MCES algorithm and do not require any of the conditions (i) - (dét). Hence, our results do not have the three draw- backs listed above, and also allow for no discounting (as in the stochastic shortest path problem). However, our proof's 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 stochas- tie feed-forwarr environments such as Blackjack (Sutton& & Barto 2018) and also all deterministic MDPs, such gridworlds (Sutton & Barto 2018), Go and Chess (when played against fixed op- ponent 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). More examples
2

---

Published as a conference paper at ICLR 2022
provided in appendix C Moreover, if the trajectory horizon is instead fixed and deterministic, we show that the original MCES algorithm always converges (to a (ieeddeeeddent optimal policy, without any conditions 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 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 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 improv- ing our understanding on the convergence properties of the original MCES algorithm.
2 RELATED WORK
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 terminate when the terminal state reached, and thus the episode length is not fixed at H and may have 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 infinite- horizon 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 BBertsekas & Tsitsiklis (1991) and references therein; also 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.
Swwwing/Suttonn/ Sutton & Barto (018)) we instead reserve the term episodic MDPs for MDPs that
Convergence theory for RL algorithms has a long history. For the infinite-horizon discounted cri- terion, by showing that Q-learning is form of stochastic approximations, [Titsiklis) (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 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 op- timal Q values almost surely. Yu & Bertsekas| (2013) prove that the sequence of Q-learning iterates 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 Sutton & Barto ( (1998), Bertsekas & Tsitsiklis (196),, and Tsit- siklis (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 (199)), 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). Re- cently, 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 (di) - (dāt) stated in the introduction, and their proofs employ the stochastic ap- proximations methodology in Tsitsiklis (1994). The results we develop here are complementary to
the results in lis (2002). [Chen (2018), and Liu (2020), in that they do not require the strong
algorithmic assumptions (ii) (ii1) 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 (c.g. see Jin et al. (2018)) and also for Monte Carlo approaches (e.g., see Kocsis & SSzepeváári (006) Azar al. (2017)) 7p). To the best of our knowledge, these regret bounds assume finite-horioon MDPs (for which the optimal policy is time-dependent) rather than the terminal-state episodic MDPs considered here.
3

---

Published as a conference paper at ICLR 2022
3 MDP FORMULATION
Following the notation of Sutton & Barto 2018). finite Markov decision process is defined by a finite state space S and finite action space A, reward function r(s, a) mapping S A the reals, and dynamics function p(-|s, a), which for every E S and a E A gives a probability distribution over the state space S.
A (deterministic and stationary) policy т is mapping from the state space S to the action space A. We denote (s) for the action selected under policy when state Denote ST for the state at time under policy т. Given any policy the state evolution becomes well-defined Markov chain with transition probabilities
P(S s' S' =) s) p(ssss
3.1 RETURN FOR RANDOM-LENGIE EPISODES
As indicated in Chapters 4 and 5 of Sutton & Barto 2018), for RL algorithms based on MC meth- ods, we assume the task is episodic, that is "experience 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 maze, or any sort of repeated interaction". Chapter 4 of Sutton & Barto (2188) further states: "Fach episode ends in special state called the terminal state, followed by 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 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 possible cycling, will clearly be reached by the optimal policy. Another example of an episodic MDP, discussed at length in Sutton and Barto, "Blackjack". Here create terminal state which is entered whenever the player sticks goes bust. For Blackjack, the terminal state will be reached by all policies. Let denote the terminal state. (If there multiple terminal states, without loss in generality they can be lumped into state.)
When using policy æ to generate an episode, let
T min ST =}
be the time when the episode ends. The expected total reward when starting in state is
Ux (s) E rSS (S7)))
Maximizing corresponds the stochastic shortest path problem (as defined in Bertsekas & Tsitsiklis (1991) Bertsekas ), for which there exists an optimal policy that is both stationary and deterministic (for example, Proposition 2.2 of Bertsekas (2012)).
At the end of this paper we will also consider the finite horizon problem of maximizing:
H
E
rS ग
=
t=0
where H is fixed and given horizon. For this criterion, it is well-known that optimal policy π (s)) = (T(s, .),..., (Ts If)) non-stationary. For the finite-horizon problem, is not required that the MDP have terminal state.
3.2 CLASSES OF MDPS
We will prove convergence results for important classes MDPs. For any MDP, define the MDP graph as follows: the nodes of the graph the MDP states; there is directed link from state to if there exists an action a such that p(s'|s a) > O.
We say environment is Stochastic Feed-Forward (SFF) if state cannot be revisited within any episode. More precisely, the MDP is SEF its MDP graph has no cycles. Note that transitions permitted to be stochastic. SFF environments occur naturally in practice. For example, the
4

---

Published as a conference paper at ICLR 2022
Blackjack environment, studied in detail in Sutton & Barto (2018). is SFF. We say environment Optimal Policy Feed-Forward (OPFF) if under any optimal policy state is never re- visited. More precisely, construct sub-graph of the MDP graph as follows: each state is node in the graph, and there is a directed edge from node s to s' if p(s' 8,, 2,a")) > 0 for some optimal action a" The MDP is OPFF if this sub-graph is acyelic.
An environment said to be a deterministic environment if for any state & and chosen action a, the reward and subsequent state s' are given by two (unknown) deterministic functions r(s, and s' g(s, a). Many natural environments are deterministic. For example, in Sutton & Barto 2018 environments TiceTac-Toe, Gridworld. Golf, Windy Gridworld, and Cliff Walking are all deterministic. Moreover, many natural environments with continuous state and action spaces are deterministie, such as the MuloCo robotic locomotion environments (Todoroy et al. 2012). It easily seen that all SFF MDPs are OPFF, and all deterministic MDPs for which the optimal policy terminates w.p.1 are OPFF.
MONTE CARLO WITH EXPLORING STARTS
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.
The MCES algorithm is given in Algorithm T
Algorithm is consistent with the MCES algorithm in Sutton & Barto 2018 and has the following important features:
Q(S,, At) is updated for every St, At pair along the episode, and not just for So, Ao as required in (Tsitsiklis 2002).
The initial state and action can be chosen arbitrarily (but infinitely often), and does not have to be chosen according to uniform distribution as required in (Tsitsiklis) 2002).
For simplicity, we present the algorithm with no discounting (i.e., y 1). However, the subsequent proofs go through for any discount factor 7 < 1. (The proof in Tsitsiklis (2002) requires 7 < 1.)
We emphasize that although the results in Tsitsiklis (002) 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 MCES
1: Initialize: π (s) E A. Q(s. a) R, for all s E S,a E A, arbitrarily; Returns(s: (s, a) f empty list, for all E S,a E A.
2: while True do
3: Choose S, E S, Ag E s.t. all pairs are chosen infinitely often.
4: Generate episode following Su, S1, AI...., Sr Ar Sr.
5:
G+0
6:
for 1,7
d
7:
G G + r(S,,
8:
Append Go Returns At)
9:
Q(S,, Ax) + average Returns(SS,, A.))
T(S)) + argmayy ())
We begin with the following lemma, whose proof can be found in Appendix A.
Lemma 1. Let X1, X2.... be sequence of random variables. Let T be random variable taking values the positive integers, and suppose P(T < x0) = 1. Suppose that for every positive integer Xay Xnth.... are i.i.d. with finite mean x" and finite variance when conditioned T Then P(lim N EN X; =1.
5

---

Published as a conference paper at ICLR 2022
Say that the MCES algorithm begins iteration u at the uth time that episode runs, and ends the iteration after Q and x have been updated (basically an iteration in the while loop in Algorithm [ Denote by Qu a) and (s) for the values of Q(s, a) and T(s) at the end of the wth iteration.
For simplicity, assume that the MDP has a unique optimal policy n², 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" a) and x T. converges to " (s) for all E S and all E A w.p.I.
Proof. Because the MDP is SFF, its MDP graph is a Directed Acyelic Graph (DAG), So we can re-order the N states such that from state 8& and selecting any action, we can only transition to state in (8*+1,...,&N Note state 8N is the terminal state, from state 8N-1, all actions lead to 8N-
The proof is by backward induction. The result is trivially true for sN- Suppose it is true for all states in [$8+1)...,8N and all actions a E A. We now show it is true for 8% and all actions a E A.
We first establish Qu a) converges to q" (sk; a) for all E A w.p.1. Let T be the iteration u when (s) has converged to T. for all E ( _N.. By the inductive assumption, P(T < oo) 1. Let a E A be any action. Now consider any episode after time in which we visit state and choose action a. Because the MDP is SFF, the next state will be in {Sk+11.... s. and because of the inductive assumption, the subsequent actions in the episode will follow the optimal policy nt until the episode terminates. By the definition of 9º (sk, a), the expected return for such an episode is equal (sk, a). Let G, denote the return for ($g, a) for the nth episode in which (sk, a) appears. After time T, these returns are i.i.d. with mean q" (Sk, a). Therefore, by Lemma I
1 N
lim Qu(sk, = lim 10000
Σ
Gn = ("k w.p.1
(4)
N-000
N
n=1
It remains to show that Tu (sk) converges to (sk) w.p.1. Define a x² (8x). Since x² is the unique optimal policy, we have:
('(sk, (4 a)
(5)
for some e' > 0 for all a + a*.
Let Q be the underlying sample space, and let A be the set of all w E Z such that Quks,, a) (w)
converges to q" (*x, a) for all E A. By (4) P(A) = 1. Thus for any A and any >> 0, there exists a u' (depending on w) such that u 2 u' implies
(g" a) Qu(sk; a)(w) Se for all a E A
(6)
Let be any number satisfying 0 < < <'//2, let w E A, and u' be such that ( is satisfied for all
u 2 w'. It follows from (5) and (6) that for any u 2 w' we have Qu(sk, ("ss,a")ee (w) 2 ("k, -E
(7)
2 (sk, a) + c -c
(8)
2 Qu(kk, a)(w) + e' 2x
(9)
Qu (w)
(10)
for all * a". Let u be any iteration after w' such that state 8 is visited in the corresponding episode. From the MCES algorithm, (w) = arg max, Qu(sk, (w). Thus the above in- equality implies n. (*x)(w) = a": furthermore, n. (#x)(w) will be unchanged in any subsequent iteration. Thus, for every E A, (x.))) converges to a". Since P(A) 1, it follows (xx)) converges to a" w.p.l., completing the proof.
We make the following additional observations: (1) It is not necessary to assume the MDP has 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.

---

Published as a conference paper at ICLR 2022
5 OPFF MDPS
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 terminate and the returns will simply not be used. We also initialize all Q values to be -oo, so that the policy will always prefer an action that has led at least one valid return over actions that never yield 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-visin MCES for OPFF MDPs
1: Initialize: (s) A, ((s, a) -c, for all s S, a E A, arbitrarily; Returns(s, (8; a) f- empty list, for all s E S, A.
2: while True do
3: Choose Su E S, Ag E s.t. all pairs are chosen infinitely often.
4: Generate an episode following æ: Sq, Ag, St, A...... AT ST
5: if the episode does not end in less than M time steps then terminate the episode at time step M
6:
7:
else
8:
G
9:
for = T T do
10:
G - G+
11:
if A, does not appears in S Ag. S1, Al S,.,,,,,,, A-- then Append G to Relurns (e,, A,) QS,, A1) averagel Returns (S,, A,)) (S,)) + arg max, Q(S(, a)
12:
13:
14:
Theorem 2. Suppose the MDP is OPFF. Then Qu(s,a) converges to (s, and (s)s) converges to x² (s) (s) all and all a E Awp.l.
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 depend- ing on current state and action). Note for OPFF MDPs, our proof has to take more sophisticated approach since now transition to arbitrary state by taking any non-optimal action.
FINITE- MDPs
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 finite horizon set H {0, 1, ..... 1,.... H). finite state space S, a finite action space A, reward function
r(s, f, a) mapping S x to the reals, and a dynamics function p(-|s, t, a). which for every s S, E A and time step t, gives 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 x (s, t) will also be time-dependent, even if p(-|s, a) and r(s, f, do not depend on
The MCES algorithm for this setting is given in Algorithm 3 Note that in this version of the algorithm, during exploring starts need to choose So E An A, and an h E [0, H)..
Corollary 1. Suppose we are using the fiittehorizon optimization criterion. Then Qu(s, 1, a) verges to 9" (s,t,a and (s, t) converges to Tt" r t) for all s E S, E H and all a E A w.p.l.
Proof. A finite-horizon MDP is equivalent standard MDP where the time step is treated part of the state. Since the number of time steps monotonically increases, this MDP is SEF. Thus the convergence of MCES for the finite-horizon MDP setting follows directly from Theorem

---

Published as a conference paper at ICLR 2022
Algorithm 3 MCES for Finite-Horizon MDPs
1: Initialize: (ss, t) A. Q(s, t, R. for all E S,t E 00 H.H A, arbitrarily; Returns(s, t, a) < empty list, for all & E S,t e [0, H A.
2: while True do
3: Choose So E S, A E A. E [0, HJ, s.t. all triples are chosen infinitely often.
4: Generate an episode following æ: Sh, An, S Auti..... S AH-1, SH.
5:
G
6:
fort - 1, 2, .,... do
7:
G +r
8:
Append G Returns St,, Ad)
9:
Q 1, Ar) + averagel RRelurss A.))
10:
TSe,,) 1) < arg max, Q
EXPERIMENTAL RESULTS
In addition to the theoretical results, we also provide experimental results to compare the conver- gence 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- "multi-update" variant, and the modified MCES the "first-udatte" variant. We consider two classical environments: blackjack and stochas- tic cliffwalking. We will briefly discuss the settings and summarize the results. A more detailed discussion, including additional results on Q-Learning is provided in appendix D and F
For blackjack, 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 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 deck of 52 cards; and uniform-ing 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 [ shows uniform initialization converges faster than standard initialization, and the multi-update variant is faster than the first-update variant for both initialization schemes.
the same problem setting discussed in Sutton & Barto (1998) Blackjack
Uniformnt Mubi-pphtte
brtferm in Find update
Suandaro-nnt, M.Bi-cddtt
Sta vitro init First apdiee
-207
-20
-311
(a) Performance
(b) Average absolute Q update
Figure 1: (a) Performance and (b) average of absolute Q update error (in log scale) for blackjack. Multi-update variant has better performance and lower Q error.
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 -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 downwards, making OPFF MDP. We now compare the MCES
8

---

Published as a conference paper at ICLR 2022
variants and measure the convergence rate in terms of the performance and the average LI distance between the current Q estimate and the optimal Q values. The results are summarized Figure the training curves averaged across number of different gridworld sizes and wind probabilities.
Results show that multi-update MCES consistently learns faster than first-update MCES.
107
275 10
25H 10
Roformarce
Refermance
19
1.25x10
200000
(a) OPFF Cliff Walking, Performance
(b) OPFF Cliff Walking, average L1 distance optimal values
(c) SFF Cliff Walking, Performance
(d) SFF Cliff Walking, average L1 distance optimal values
Figure 2: Performance and the average L1 distance to optimal Q values, OPFF and SFF cliff walking, the curves are averaged over different gridworld sizes and wind probability settings.
Our experimental results show that the multi-update MCES converges much faster than the first- update 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.
8 CONCLUSION
Theorem 2 of this paper shows that as long as the episodic MDP is OPFF, then the MCES algo- rithm 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 methodol- ogy is also novel, and can potentially be applied to other classes of RL problems. Moreover, our methodology also allows
establish convergence results for finite-horizon MDPs simple corollary of Theorem 2. Combining the results of Bertsekas & Tsitsiklis (1996). Tsitsiklis 2002), Chen (2018), Liu (020)) and the results here gives Figure 3 which summarizes what now known about convergence of the MCES algorithm. In appendix F we also provide a new counterexample where we prove that MCES may not converge in non-Onnn OPF-OPFF episodic environment.
OPFF MDPs
Non-OPFF MDPs
Q updale et
Originel MCES
No Convergence
Figure 3: MCES has been studied for two classes of algorithms: Q-values updated at the same rate Tsitsiklis 2002): Chen (2018); : Liu (2020) and the original, more flexible algorithm, which does not require the conditions (1) and (tt)) stated in the Introduction. We partition the episodic MDP space into two classes: OPFF MDPs and non-OPFF MDPs. As shown in the figure, this leads to four algorithmic/MDP regions. Convergence is now established for the three blue shaded regions, for all discount factors y & In the other region, it is known that at least for some non- Non-OPFF MDPs, convergence does not oceur (shown the orange oval region). A new counterexample in episodic MDP and additional discussion are provided in appendix
The results in this paper along with other previous works (Tittsiklis) 2002 Chen 2018 Liu 2020
make significant progress in establishing the convergence of the MCES algorithm. Many cases of practical interest whether there exist conditions on MDPs that are weaker than the OPFF, and can still guarantee the convergence of the original MCES algorithm.
covered by the conditions in these papers. It still remains open problem

---

Published as a conference paper at ICLR 2022
REFERENCES
Mohammad Gheshlaghi Azar, lan Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference Machine Learning, pp. 263-272. PMLR, 2017.
Dimitri P Bertsekas. Dynamic programming and optimal control, volume 2. Athena scientific Belmont, MA, 4 edition, 2012.
Dimiuri P Bertsckas and John N Tsitsiklis. An analysis of stochastic shortest path problems. Math- ematics of Operations Research, 16(3):800-595 1991.
Dimitri Bertsekas and John N Tsitsiklis. Neuro-dynamic programming, volume Athena Scien- tific Belmont, MA, 1996.
Xinyue Chen, Zijian Zhou, Zheng Wang, Che Wang, Yanqiu Wu, and Keith Ross. Bail: Best-action imitation learning for batch deep reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pp. 18353-18363, 2020.
Yuanlong Chen. On the convergence of optimistic policy iteration for stochastic shortest path prob- lem. arXiv preprini arXiv: 08766, 2018.
Tommi Jaakkola, Michael Jordan, and Satinder P Singh. Convergence of stochastic iterative dy- namic programming algorithms. In Advances in neural information processing systems, pp. 703- 710, 1994.
Chi Jin, Zeyuan Allen-Zhu, Sehastien Bubeck, and Michael Jordan. q-learning provably effi cient? In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
Levente Koesis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning, pp. 282-293. Springer, 2006.
Jun Liu. On the convergence of reinforcement learning with monte carlo exploring starts. arXiv preprint arXiv:2007.10916, 2020.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
David Silver. Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, :554 359, 2017.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre. Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):11444 1144, 2018.
Richard S Sutton and Andrew G Barto. Introduction to reinforcement learning, volume 2. MIT press Cambridge, 1998.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physies engine for model-based control. In Intelligent Robots and Systems (IROS), 2012 JEEE/RSJ International Conference on, pp. 5026- 5033. IEEE, 2012.
John N Tsitsiklis. Asynchronous stochastic approximation and q-learning. Machine learning, 16 (3):185-200) 1994.
John N Tsitsiklis. On the convergence of optimistic policy iteration. Journal of Machine Learning Research, 30ul))59-72, 2002.
Denis Yarats, Rob Fergus, Alessandro Lazaric, and Lerrel Pinto. Mastering visual continuous con- trol: Improved data- augmentedd reinforcement learning. arXiv preprint arXiv:2107.09645, 2021.
Huizhen Yu and Dimitri Bertsekas. On boundedness of q-learning iterates for stochastic shortest path problems. Mathematics of Operations Research, 38(2):209-227) 2013.
10

---

Published as a conference paper at ICLR 2022
A
PROOF OF LEMMA 1
Proof. We have
1 N
P lim
Σ x; = x*)
N-000
N
PC lim
Σ
x P(T =n)
N-000 i=1
N
n=1
Jim P(
R-1
X
1 N
Σ = ="V=====
+00
N
Σ
X; = x I = n P(T =1
N
==1
1
The first equality follows from P(T < = 1. The last equality follows from the conditional i.id. assumption and the Strong Law of Large Numbers. Note we can apply the Strong Law of Large Numbers here because as stated in Lemma T we have the assumption that Xn, X Xn+1..... are i.i.d. with finite mean and finite variance.
B PROOF OF THEOREM 2
Proof. Because the MDP OPFF, its optimal policy MDP graph is DAG, so we can re-order the only transition to state in
states such that from state sy and selecting the optimal action dg. {sk-1..... }. }. Note that state SN is the terminal state, and note that from state SN-1 1 the optimal action only leads to SN-
We first show that for all k L,...,, N, Qu aj)) converges to q" (5k, (sk,af) and that n. (8x) con- verges to x² (sk), w.p.1. Once establish this convergence result for all k 1...., .N. will then complete the proof by establishing convergence Qu(sk, a) for arbitrary actions a. Note that the organization of this proof slightly more complicated than that of Theorem due the weaker OPFF assumption.
The result is trivially true for 8N- Suppose now Qu az) converges q" (85,47) and that Tu (s;) converges to x" (sj), w.p.1 for all j k 1, 1,... N. We now show Qu(sk, di) converges to q" (5k, (g) and that T. (sk) converges to क" (sx), w.p.1. Denote a" dx.
Let T be the iteration u when (s) has converged (s) for all s E {sk+1,-... 8N). By the inductive assumption, P(T < c0) 1. Now consider any episode after time T that for some timestep in this episode, we arrive state sy and chooses the optimal action a'. Because the MDP is OPFF, the next state will be in {sA+1...., ), and because of the inductive assumption the subsequent actions the episode will follow the optimal policy within a finite number of steps. By the definition of 9" (SE,, a"), the expected return for ($2, a*) in this episode is equal to q"(8n, a"). Let G, denote the return for nith episode in which we visit 88 and chooses optimal action a". Note that after time T, these returns are i.i.d. with mean g" (sk, a"). Therefore, by Lemma I
until the episode terminates
1 N Σ G, 4- (*k, w.p.1
lim Qu(skaa")= = lim 100000
(11)
No000
N
n=1
Next we show that n. (Sk) converges to x (sk) = a w.p.1. Since x" is the unique optimal policy, we have:
q' (sk,a") 2 9"' (sk, a) +e'
(12)
for some e' > 0 for all + 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".

---

Published as a conference paper at ICLR 2022
Consider state 8y and arbitrary action A. From the MCES algorithm, have Qu Thu E1=1 G₁, where Lu the total number of first-visit returns used to compute (sk. a) up
+. Jo through the uth iteration, and G₁ the return value for the Ith such iteration. Let denote the (finite) set of all deterministic policies, L denote the number of first-visi returns used to compute (ak a) up through the uth iteration when using policy オ, and Gy, S 1 S L, denote the /th return value when policy и is used. We have
au(
Σ
Gt
(13)
La
1=1
GT)
(14)
TEll
1=1
By the law of large numbers, know that for any policy such that L + oo have w.p.1
E G = (sk, a) S q" (s):
lim
= L
(15)
where 9r (Sk: a) is the action-value function for policy æ. The inequality in (15) follows from the definition of q (s, It follows from (14) and (5) that w.p.1
lim sup Qu(sk S (sk. a) for all 20000
(16)
Note that in the OPFF setting, in the special case that no valid return has been obtained for (sk, a). then (8k, a) - I q" (8k, a), so the above inequality still holds.
Let Ω be the underlying sample space, and let A Ω be the over which (16) holds. Note that P(A) = 1. Thus for any w E A and any > 0, there exists u' such that u 2 u implies
Qu(sk, (ww S 9" (sk: a) + for all E
(17)
Let be any number satisfying 0 < E < e//2, let w A, and u' be such that 17 is satisfied for all
2 u'. It follows from 11 and 117 that for any 2 u' we have
Qu(sk, a" (w) 2 q (sk, a*) -
(18)
2 q" (sk. + c' -
(19)
2 Qu(aki a)(w) + 2E
(20)
Qulsk, a)(w)
(21)
for all a * a". Let be any iteration after u' such that the episode includes state Sk. From the MCES algorithm, (w) arg max, Qu (w). Thus the above inequality implies (a(8k (s)))((w) a": furthermore, Tu (sx) will be unchanged in any subsequent iteration. Thus, for every w A, m. (w)) converges a". Since P(A) = 1, it follows (a.(s) converges to a" w.p.1.
We have now shown that for all k = 1,..., N. (sk: a converges to q" (Sk, (5))a{) and that (sx) converges to T" (sx), w.p.1. remains to show convergence of Qu a) to (s, for arbitrary state 8 and action a. Let u' be such that 2 u', (s) T" (s)) for all E 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 n². Thus the expected return for (s, in this episode is q" (s. We can thus once again apply Lemma to show Qu(s. (8, a) converges to 4" (8,8)) w.p.1, thereby completing the proof.
12

---

Published as a conference paper at ICLR 2022
C ADDITIONAL DISCUSSION ON PRACTICAL OPFF TASKS AND MC ALGORITHMS
C.1 OPFF AS PRACTICAL SETTING
OPFF MDP is a large and important family of MDPs. There are many natural examples of OPFF MDPs, for example, Blackjack. windy gridworlds and MuJoCo robotic locomotion discussed in this work. Also note that if a task involves any monotonically changing value as part of the state, then it is also OPFF. For example, when time added the state handle finite horizon criteria, then the MDP becomes OPFF whether not the original MDP is OPFF. Here we give extended list real-world practical problems that fall into OPFF MDPs:
Operating robot or datacenter with a power budget;
Driving car with a given amount of fuel or to reach target within a time limit;
Manufacturing product with limited resources;
Doing online ads bidding with fixed budget;
Running recommendation systems with limited amount of recommendation attempts;
Trading to maximize profit within a time period, and more;
For the MuloCo environment, note if we treat it as an episodic MDP (for example, if the task is run towards a goal, and the episode terminates when the goal is reached) instead of an infinite- horizon task (for example, if the task is to keep running indefinitely), then it falls into the category of OPFF because the simulation deterministic. As discussed in main paper, all deterministic episodic MDPs are OPFE
C.2 How ALPHAZERO RELATES TO MONTE CARLO METHODS
The AlphaZero learning process can be roughly seen as nested loop: there is the outer loop where the agent starts the game from an empty board and plays the end of the game, and then for each state on this trajectory, there is an inner loop of Monte Carlo Tree Search (MCTS), which is planning phase that starts from state s. After the planning finishes, single physical move made (in the outer loop). When we consider all algorithmic components of AlphaZero, it is clear that AlphaZero very different from MCES (even the MCTS algorithm alone is very different from MCES). Although MCES and AlphaZero do not do the same thing, they share some important similarities on high level.
In appendix E. we further provide discussion on the use of Monte Carlo methods in recent liter- ature, together with an additional experimental comparison between the MCES algorithm and the Q-Learning algorithm.
13

---

Published as a conference paper at ICLR 2022
D ADDITIONAL EXPERIMENTAL DETAILS
D.1 BLACKIACK ENVIRONMENT
Here we give more in-depth discussion on our blackjack experiments. The code for the experiments provided
We use the same problem setting as discussed in Sutton & Barto 1198). 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 counted as either or 11. If the player holds an ace that can be counted 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), stops (sticks), if the player's 's sum exceeds 21 (goes bust), then the player loses. After the player sticks, The dealer will hit or stick according 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 draw if both sides have the same sum. When the episode terminates, the reward is 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 previously visited state (if the player has a usable ace, the player can move into state with unusable ace, but not vice-versa). Therefore blackjack is a stochastic feed-forward (SFF) environment.
fixed policy: he sticks on any sum of 17 greater and hits
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 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) 10) and whether the player has 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.c., 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 simply the difference between the Q values before and after Q update. For each episode, the average absolute Q update error is averaged over all state-action pairs that are updated in this episode. all figures, the solid curve shows the mean value over 5 seeds, and the shaded area indicates the confidence interval.
In F 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 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 uulti- MCES variant.
14

---

Published as a conference paper at ICLR 2022
D.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 the bottom row of the gridworld).
In our setting, the agent can move in four directions (right, up. left, down), and gets a reward for each step it takes, -100 for falling into the cliff, and O 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 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 Pz. If the agent is in the SEF 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 '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 the right, and the wind can only blow the agent one step upwards, or downwards. This is shown in Figure by the arrows near the position Pi, if the agent 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 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.
D.2.1 CLIFF WALKING EXPERIMENTAL RESULTS
We use performance and the average LI distance to the optimal Q value as metrics for the con- vergence 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 and [ We present results on gridworld sizes of 6, 12 9, 16 x 12 and wind probability 0.3, 0.5.
In Fig 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.
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.
In Fig 7 and Fig g
Results in both cliff walking environments, and across all tested gridworld size and wind probabil- ity consistently show that multi-update MCES learns faster than first-update MCES. These results show there is indeed 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 andd each row shows performance for a gridworld size and each column shows wind probability, if go from the top left figure (figure (a)) to the bottom
15

---

Published as a conference paper at ICLR 2022
P1
P2
S
The Cliff
G
Figure 4: Cliff Walking Environment Illustration: The grid world contains of start state, goal state and a cliff area between them. the OPFF cliff walking setting with wind probability IP.. when the agent is Pi and moves one step to the right, it will take additional step upwards or downwards, each with probability E.2 and not take this additional step with probability the SFF cliff walking environment with wind probability Fw. when the agent is at P2 and takes one step up, will take an additional step towards one of the four directions, each with probability Eu, and take additional step with probability 1 P w-
P.. In
right figure (figure (i)), we see that the performance gap tends to become bigger. This result shows that taking more updates the value estimate can be important especially complex tasks with more randomness.
16

---

Published as a conference paper at ICLR 2022
Abs DMT to OptimalQ
Alx to
201
201
10"
Alx
20000 40000 00000 30000 100000
20000
40000 60000 80000 100000
20000 40000 60000 80000 100000
(a) 8x6 grid, 10% wind
(b) 8x6 grid, 30% wind
(c) 8x6 grid, 50% wind
107
Q
R2s on to 92000 Senmie 9
buff Pylimal
291-
201-
1.0
0
20000 40003 60000
80000 100000
20000
40000 60000 80000 100000
20000
40000
00000
80000 100000
(d) 12x9 grid, 10% wind
(e) 12x9 grid, 30% wind
(I) 12x9 grid, 50% wind
102
101
10a
put-update
Rist-updte
Optima
AVS Offic Optmaa
te Opiimal
10a
10-
20000
40003
100000
20000 40000 60000
100000
40003
60000
100000
(g) 16x grid, 10% wind
(h) 16x12 grid, 30% wind
16x12 grid, 50% wind
Figure 5: OPFF Cliff Walking: average LI distance to optimal Q values, with different grid world sizes and wind probabilities. Y-axis is log scale.
17

---

Published as a conference paper at ICLR 2022
-10
-10
-20-
-90
-30
Re-forance
-30
Pe Pe-forencce
30
-50
-60
-50
-70
20000
40000
66000 88000 100000
0
2000
40000 60000
80000 100000
20000
40000
50000
80000 100000
(a) 8x6 grid, 10% wind
(b) 8x6 grid, 30% wind
(c) 8x6 grid, 50% wind
-20
-40
Porormance
Perfommanc
-50
-60
-100
100000
80000
(d) 12x9 grid, 10%
(c) 12x9 grid, 30% wind
(I) grid. 50% wind
-20
-40
-10
Performanc
-60
-50
Pe
Rubiypdate
-100
-100
fint-ppdtte
20000 40000 60000 806o0 100000
20000 40000 sCóCo 80000 100000
20000 40000 60000 andoo 100000
(g) 16x12 grid, 10% wind
(h) 16x 2 grid, 30% wind
(i) 16x12 grid, 50% wind
Figure 6: OPFF Cliff Walking: Performance, with different grid world sizes and wind probabilities.
18

---

Published as a conference paper at ICLR 2022
3x 10
30
Alx Optinal
Abs DMT to Optinale
Optimals
3 10'
2x100
2x 101.
20
101
101
20000 40000 60300 80030100000
0
20000 40000 60000 acco0
100000
20000 40000 60000 80000 100000
(a) 8x6 grid, 10% wind
(b) 8x6 grid, 30% wind
(c) 8x6 grid, 50% wind
2.5x10 -
28 1.6
3810
2.2x10
Sytimal
Ros Dirt Optine
Optimall
105x10
18x
101
14x10
100
12x10'
20000 40000 00000 50000100000
20000 4000 60000 B0001000000
20000 43000 60300 88000 100000
(d) 12x9 grid, 10% wind
(e) 12x9 grid, 30% wind
(I) 12x9 grid, 50% wind
2.4
2.2 10
Lo Ogimm
2xx10*
Oo Opcmal
14
2.2x10'
2x:10
1.6x10
Abs bill
1.8x101
14x10'
16
Mut- update
Iirstsppiate
20000 enino 50000100000
12x10'
20000 40000 Boúco 8odco100co0
20000 40000 #0000100000
(g) 16x grid, 10% wind
(h) 16x12 grid, 30% wind
16x12 grid, 50% wind
Figure 7: SFF Cliff Walking: average LI distance to optimal Q values, with different grid world sizes and wind probabilities, y axis is log scale.
19

---

Published as a conference paper at ICLR 2022
40
-40
Pe-orrancc
Performence
Peformance
-50
-80
900
-100
20000 40000
60000 80000 100000
20000 40000 60000 80000 100000
20000
40000 sed0o sodoo 100000
(a) 8x6 grid, 10% wind
(b) 8x6 grid, 30% wind
(c) 8x6 grid, 50% wind
-30
-50
-50
-30
Peformance
-60
-70
Rerfrmmncc
-90
-90
-100
-100
-100
100000
80000
(d) 12x9 grid, 10%
(c) 12x9 grid, 30% wind
(I) grid. 50% wind
50
Mull--pdate
Rist: spd--upddtee
Performancs
70
-70
-0
-80
-50
90-
-100
20000 40000 60000 apdoo 100000
20000 40000 SCÓCO 80000 100000
20/00 40000 60000 andoo 100000
(g) 16x12 grid, 10% wind
(h) 16x 12 grid, 30% wind
(i) 16x12 2 grid, 50% wind
Figure 8: SFF Cliff Walking: Performance, with different grid world sizes and wind probabilities.
20

---

Published as a conference paper at ICLR 2022
E ADDITIONAL EXPERIMENTS ON Q-LEARNING
qin this section, we additionally compare the multi-update MCES variant to the Q-learning algo- rithm with different learning rates and discount factors. The results summarized in Figure 9 the training curves are averaged across number of different gridworld sizes and wind probabilities. Results show that in the CliffWalking environment, the optimal hyperparameters for Q-Learning are different in each environment. With the right set of hyperparameters Q-Learning can significantly outperform the multi-update variant MCES. This observation is consistent with the strong sample efficiency of a large number of Q-Leeaning--aseee methods in recent deep reinforcement learning lit- erature. Note that some of the most effective deep reinforcement learning methods, such as DrQv2 Yaraat et al. 2021), use variant of the n-step TD method, which can be seen generalization of both MC and one-step TD methods, as discussed in Chapter 7 of Sutton & Barto (2018). Popu- lar on-policy deep reinforcement learning methods such PPO (Schulman technique called generalized advantage estimation, which can also be seen as a mix MC and TD methods. In offline deep reinforcement learning, some recent methods Monte Carlo returns select a number of "best actions" and perform imitation learning, effectively avoiding some of the unique issues in offline reinforcement learning (Chen et al. 2020).
al. (211)) also use
These results show that is important to improve our understanding of both MC and TD methods, in order develop new algorithms that are efficient and performant. Detailed results for each setting
are shown in Figure 10 Figure Figure 12 and Figure
0- 001
g3.00
(a) OPFF Cliff Walking, (b) OPFF Cliff Walking, average L1 distance to optimal values
(c) SFF Cliff Walking, Performance
(d) SFF Cliff Walking, average L1 distance to optimal values
Performance
Figure 9: Performance and the average L1 distance to optimal Q values, on OPFF and SEF cliff walking, for MCES with multi-update variant and Q-Learning with different learning (a) and discount factor (g), the curves are averaged over different gridworld sizes and wind probability settings.
21

---

Published as a conference paper at ICLR 2022
to Optiimal
Abs EVr Optinal
Nlx Optlimal
(a) 8x6 grid, 10% wind
(b) 8x6 grid, 30% wind
(c) 8x6 grid, 50% wind
A2S CXP to Octino
palf Setimra
Abx to
10000
2006
2003
(d) 12x9 grid, 10% wind
(e) 12x9 grid, 30% wind
(1) 12x9 grid, 50% wind
MCES-MMI6
0.00.001.0..9
Optimal
Abs Difto Optinal
Ditto Oyginng
0:a011.00.99
000
a0.01 g0.9
20.01
(g) 16x12 grid, 10% wind
(h) 16x12 grid, 30% wind
16x12 grid, 50% wind
Figure 10: OPFF Cliff Walking: average L1 distance to optimal Q values, with different grid world sizes and wind probabilities. Y-axis is log scale.
22

---

Published as a conference paper at ICLR 2022
Performanc
(a) 8x6 grid, 10% wind
(b) 8x6 grid, 30% wind
(c) 8x6 grid, 50% wind
Perto nerfomance
Perfo
3000
20003
(d) 12x9 grid, 10% wind
(e) 12x9 grid, 30% wind
(f) 12x9 grid. 50% wind
Porformanee
Performence
MCES
Quea -n
Q-10001-0..0
Q-a011-go.w
3-30 30.0000440.
0:30.01-00.0
(g) 16x12 grid, 10% wind
(h) 16x12 grid, 30% wind
(i) 16x12 grid, 50% wind
Figure 11: OPFF Cliff Walking: Performance, with different grid world sizes and wind probabilities.
23

---

Published as a conference paper at ICLR 2022
Abs DVT Optinal
Diff Optined
to
1:300
6x30
(a) 8x6 grid, 10% wind
(b) 8x6 grid, 30% wind
(c) 8x6 grid, 50% wind
Optinnal 0
2432
Abs CMT to Optinal
Delimaa
kx37
10000
200803
10008
6000
10008
230030
3040
10000
11006
3000
(d) 12x9 grid, 10% wind
(e) 12x9 grid, 30% wind
(I) 12x9 grid, 50% wind
Abs DI Optinal
NCES: 96.th
Quuh 01-g0.54
Quac 1-g0.
0-20 021 001-q00
0.8011g00.
210000
1X000
200030
(g) 16x12 grid, 10% wind
(h) 16x12 grid, 30% wind
16x12 grid, 50% wind
Figure 12: SFF Cliff Walking: average L1 distance to optimal Q values, with different grid world sizes and wind probabilities. Y-axis is log scale.
24

---

Published as a conference paper at ICLR 2022
Performance
Performance
(a) 8x6 grid, 10% wind
(b) 8x6 grid, 30% wind
(c) 8x6 grid, 50% wind
Petto muncc
Perfor
-19
20003
(d) 12x9 grid, 10% wind
(e) 12x9 grid, 30% wind
(I) grid. 50% wind
Perommanc 00
MCES
Quid no
Q-10001-00.0
q-a01--go.w
a- 20.00.0040.
0:00001-00.0
(g) 16x12 grid, 10% wind
(h) 16x12 grid, 30% wind
(i) 16x12 grid, 50% wind
Figure 13: SFF Cliff Walking: Performance, with different grid world sizes and wind probabilities.
25

---

Published as a conference paper at ICLR 2022
F COUNTEREXAMPLE
In this section, we present a counterexample in which the MCES algorithm (4) fails to converge with a specific choice of exploring starts. The example is motivated by the counterexample in Bertsekas & Tsitsiklis (1996), where the authors considered estimating the value function in deterministic continuing- environment, In |Bettekaas & Tsitsiklis (199),, the estimated value function cycles in fixed region during the iteration with specific update rule and does not converge. However, that example is not for an episodic task. Our example is concerned with estimating the Q-function an episodic MDP setting using the MCES algorithm. We can directly apply the approach in Bertsekas & Tsitsiklis (996) to our problem without substantial modification. Moreover, in our example, each generated episode and return are stochastic. So it is more difficult confine the Q- values in a specific region than the deterministic case. These features make our example substantially different from the one in [Bertsekas & Tsitsiklis (1996). Next, we formulate the episodic MDP and describe the choice of exploring starts; then we show that the MCES algorithm 44 does not converge with such a choice exploring starts.
F.1 MDP FORMULATIOON
Let the state space be S {1,2,3) where state 3 represents the terminal state, and action space A = (m = move, = stay)- At each state with = 1,2, there are two actions, move to the other state stay. We assume that after taking each action, the system will transit the terminal state 3 with the same probability > O, where e is a small number. Therefore we have the following transition probability:
1(2 m) E, s(1[1,))= = -1-6 221 m) -,,, E, s(2 = -
(22)
p(3/i, m) =, p(3)i,s) = for i 1,2
We also assume the reward function r(i, a) to be:
r(i, m) = 0 for = 1,2
(23)
r(i, s) -1 for i = 1,2
and the return the sum of the reward with the discounted factor <
pi|1s)=11r
(1.s)=1
(2s)==1
p(2(1m)=1-rr r(1.) =
1
p(l2m)=11- r(2,))
p(]1_s)]r p(3[Lm)=e
p(3)2.s p(3)2.m)=
3
Figure 14: The MDP problem
From the above setting, easily see that there four possible stationary policies:
(a) At each state, always choose to move.
(b) At state 1, move to state 2. At state 2, stay.
(c) At state 1, stay. At state 2, move to state 1.
(d) At each state, always choose to stay.
26

---

Published as a conference paper at ICLR 2022
We denote these four policies by Ta Tb, Res and md. respectively. It is easy to that Ta is the optimal policy, and the corresponding action-value function gx. is:
as. (1,m) = 0, 4n. (1,8) qm (2, m) = O, you (2,8) =
(24)
F.2 MECS ALGORITHM WITH A SPECIFIC EXPLORING STARTS
We now apply the MCES algorithm to this MDP problem to estimate the optimal policy r*(ss and the corresponding action-value function q (s,a). a). Note that we have modified the algorithm a little so that for each episode the Q-function is updated only for the initial state-action pair (Su, Ao).
Algorithm MCES
1: Initialize: rss) E A, Q(s, a) E R, for all s E S,a a E A, arbitrarily; empty list, for all E S,a A.
Returns(s,
2: while True do
3: Choose Su E S, Au s.t. all pairs chosen infinitely often.
4: Generate an episode following ग: So, Ag, S1, Al...., ST-1, Ar ST.
5: G Eizo ('r(St, At)
6:
Append Goo Returns(S. Ao)
7:
Q(So, Ao) average (aageeR(SS [[So, An))
8:
(So) - arg max, Q(So.
The estimates for x² (s) and (s, (s, a) at the end of wth iteration are denoted by (s) and Qu a), respectively. For simplicity, we also denote Q1, m). Qu (1, s), Qu m), and Qu(2,, x) by Qum Qi Qum and Q2 respectively. Moreover, the vector (Q Qu. denoted by
Q (Qimm Qis), where i 1,2
(25)
The policy (t) is uniquely determined at each state by comparing the paired value (Q Q% )
For example, when Qis > Qim Tii) = stay. When Qis < Qim- T(1) = move. Note that once the policy is determined, the returns of the generated episodes are i.i.d. random variables. There
total four possible cases by comparing paired Q-values (Q1s, Qlm) and (Q2., Q2m The trajectory
and return of each generated by MCES algorithm 4 are listed in Table 1 and 2
State
State
Initial
Episode trajectory
Return
(1.s)
1.s.sss..
-1-y-y2
(1.m)
1.m.s22.s..
0-y-y 2
Q(Ls))Q(L.m)
Q(2.))Q(2..)
(2.s)
2s222s...
-1-y.y2
(2.m)
2.m.1......
0-y-y
(1.s)
1.s.s.s....
-1-y-y2...
(1.m)
1m2.1sss...
y-0-y2.y3..
Q(Ls)=Q(L.))
Q(2))<Q(.m)
(2.s)
2s2.m.1.....
21
(2.m)
2.m.s.s...
O-y-y
Table 1: Episode and return with different initial starts generated by the MCES algorithm when Q(1, s) > @),
27

---

Published as a conference paper at ICLR 2022
State
State
Initial
Episode trajectory
Return
(1.s)
1.s.s.m..s.2....
1-0-y2-y2
(1.m)
1.m.2.s......
0-y-y²
((L.))Q(L.)
Q(2.s)Q((2.)
(2,8)
2.8.
-1-v-y
(2.m)
2.m.1.as......
A-y?. 3..
(1.s)
1.s.m.2.m.....
-1
(1.m)
1.m.m.mm.m...
Q(..))((L.)
Q(2.))Q((..)
(2,s)
2s2.m.1.m..m.
-1
(2.m)
2.m.1.m.....
Table 2: Episode and return with different initial starts generated by the MCES algorithm when Q(1, 8) < @),
Here we give the expected returns of several cases related to our counterexample.
Lemma 2. Consider an episode generated by the MCES algorithm 4
(i) When Q(1,8) < Q11, m), Q(2, > Q(2, m), and the initial start is (1.m) or when 8) > Q(1, m), ((2,s) Q2, m). and the initial start (2, m), the expected returns qr (1, m) and qa (2, m) are the same and are equal to
-7(1 - -1 = B[G
(26)
1 I- 7E
(ii) When Q(1,)) > Q). Q(2 < Q(2, m), and initial start is (2,8), when Q(1,s) <
Q),,m), (2, > Q(2 m). and the initial start is (1, the expected returns qa, (2, s) and
qn (1, are the same and are equal
== E[G] 1 t
+ +
(27)
(it) When (11,)) > m),m)) and the initial start is (1,8), or when Q(2,8) > Q(2, m) and the initial start (2,8), 8), the expected return is
-p3 :a -1
(28)
Moreover, we have μn < P2 < P3, and the variance of the return in each case is finite.
Proof. Let Ay be the event that a generated episode terminates after taking N + 1 actions. From the formulation of our MDP problem, we have
P(AN) = c(1 e) N22
(29)
We first prove (i), in this case, the episode is the form:
m, 2, 8, 2, 8, or 2, m, 1, 1, 8,
the return of an episode that terminates after taking N + actions is
G G 71 -1 N) 1 1-9
N20
(30)
So
E
7(1 - N)
cl N = - 1-7
? +
67
= -7(1 c)
(31)
1 1-7
(1 7) +
7
N=0
28

---

Published as a conference paper at ICLR 2022
(ii) In this case the episode is of the form
1, 8, 1, m, 2, 8, 2, 8... or m, 1,8,1,111
m,
the probability density of the return is
-1) = U)) P - N+1
(32)
P(G=-1-
P(AN) c(1 for N 2 2
1 1-7
the expected return is
22 - N+1
G =
= {l c) Σ
(-1
)e(1 e)
1-7
N=2
1 - 7 N+1
{(1 -6) +
Σ
(1 b)
N=0
7
N=1
(33)
E7
1 7 + (1- 7) - 7
+ +7(1 -t)
+ cc)
7 + 76
(iii) In this case the possible episode is
1, s, 1, s, s, s... or 2,.
so the probability density of the return is
P(G - N+1
P(AN)= = c)) N
(34)
1 1-7
and the expectation is
1 - N+1
E
c(1 - c)
?
Nm0
1
07
(35)
+
1-7
(1 - 7) 7
1 1-
Moreover, have
7(1 c)
<
7 7(1 -))
(36)
1- 7 + 7/
1- 7E
By similar calculation, we can see that the second moment G of each case is finite. Therefore, the variances are also finite.
Next, we describe specific regions in Qim Q1s and Q2m-Q2- planes. The two planes and the corresponding regions are represented in Fig. 15a and Fig. [5b] respectively. In each figure, Qim- axis and Qis-axis represent the value of Q and Q% after uth iteration given the state i, where i == 1, Since (i) arg max, Qi,, a), we can see that the line 4
1: Qim Qis
(37)
is the boundary for different policies (i)). For the vector (Qim: Qi+) above the line 4, we have (i) stay. Similarly, for those below 4, have :T(i) more. In the Qim-Qua plane, we define
R₁ = {(Qim 27,) @ Qu Q" < u + 8, Qum < -b1}
(38)
R₂ (QQ). 2%.) : Qt < 112 + o. b Pi 11
(39)
29

---

Published as a conference paper at ICLR 2022
R3 = ((=((0mm Qi.): Qim < Qis: -b < Qim < -1, 17, < --}
(40)
and in the Q2m plane, we define
T {(Q2 2m:
22.) -1 < Q2
0, Q2. 1/ +0}
(41)
T2 {(Q2m Uia) -1 2m
-1 Q2 < -1]
(42)
T3 {(Q2m Q26) - PM - ô < Q 2m
< - + 6, Q2 Q2 2m Q2 < -11
(43)
T4 (Q2m 22.) - 11
Q2m < pn + 6, 22 < (2m)
(44)
Here the parameters 6 and b satisfy
0 < < m A1 - #2 p1
7
1
2(1 7) }. 2 < b1 < min (1 2p2 - 28
(45)
2
The regions R2 and Ti are nonempty y and satisfy the following condition: Condition 3.
-1-6) >
(46)
1 1-y+7e
and
1
1-7 7 TE 2(1-7) 7(1 -
-10
-1>0
(47)
Remark 4. We claim that there exist 7 and that satisfy Condition 3
Here we give one way find
suitable and Let the ratio 1-1 = 10, then 1-2 and
10
7(1 - 1-7 + 10 10- 77)
7 +1
as approaches 1, (9++)
10->(9+7) approaches infinity. So we can choose y close to (then c close to
0) such that -{(1-)_ second inequality, similarly
1-7t7e > 2. Particularly, we can choose 0.7 < < 1 such that 46 holds. For the
+ 107
7 2(1-7)
2(72 97 10)
it approaches to infinity as 7 approaches So see that Condition 3 will hold for all 0.7 < when 6 (1 7)/10.
215
Qzs
4
l
+
-1
Qim
Qzm
T3
-1-8
1
-1
18
2
R₁
R₂
Tq
Tj
8
(a)
Q2m-QQ (b)
Figure 15: R4 and T. are blue regions in Qim-Q1s plane and Q2m- Q2a plane
Recall that QT = (Qt 1t,) and Q = (Q%m. Q%.). Assuming that Q and Q are initialized in Rí and Tı, respectively, now describe the specific choice of exploring starts.
30

---

Published as a conference paper at ICLR 2022
Exploring starts 5. We initialize Qi and Q3 to be in R1 and Tı, respectively. We then repeat the following 8 steps over and over again:
1. Keep choosing (1, m) as the initial state-action pair and update Q(1, m) until Qi enters R2.
2. Keep choosing (2, s) as the initial state-action pair and update Q(2, until Q3 enters T2.
3. Keep choosing (1, s) as the initial state-action pair and update Q(1, s) until Qi enters Rg.
4. Keep choosing (2, m) as the initial state-action pair and update Q(2, m) until Qł enters Ts.
5. Keep choosing (1, s) as the initial state-action pair and update Q(1,s) until Qi enters R2.
6. Keep choosing (1, m) as the initial state-action pair and update Q(1, m) until Qi returns R1.
7. Keep choosing (2, as the initial state-action pair and update Q(2, s) until Q3 enters T4.
8. Keep choosing (2, m) as the initial state-action pair and update Q(2, m) until Q3 returns
to Tı.
Note that in each of 8 steps, only one of the values Q(1, Q(1,s), Q(2, and Q s) changes. All others remain constant.
The trajectories of Qf and Q during the iteration are visualized in Fig. tively.
16a and Fig. 16b
respec-
O1s
Qzs
4
22
2
181
-1
-R
-8
Qim
Qzm
1
R3
T3
T2
18
22
R
R₂
-82
T4
Т
42
(a) The trajectory of Qf
(b) The trajectory of Qž
Figure 16: Trajectories of Q-values during the iteration
Next, we show that the MCES algorithm does not converge with the exploring starts 5 Precisely, we have the following result
Theorem 6. Given 7 and satisfy the condition suppose that Qi and Q are initialized in Rı and Tú. respectively. Following the MCES algorithm (4) with the exploring starts [ the trajectory
of Qt forms cycle according to Ri + R2 Ra
+ R2 - Ri almost surely, and the trajectory Ta + Ti almost surely. Thus, Qu(s, a) does
of Q forms a cycle according to Ti - Ta - Ta
not converge with probability 1.
Proof. Step 1. Start with (1, m)
When Q R1 and Q Tı. we have Q(1, s) < Q(1, m) and Q(2,s) < Q(2, m), the generated episode is just
1, m, m, m...
31

---

Published as a conference paper at ICLR 2022
so the return is always 0. During the iteration, Q increases and approaches according to
Qi @ Qt
1 -.
(48)
n
Here denote the number of stored -aauus after the (u+ 1)-th iteration. Since when Qf R1, Qim < bbb -2, and n 2 2, we have
Qim (1 1 QQ < <1 (1- 2-)
(49)
So when Qi E R1, we have Q < -1, and Qi will stay in R₁ or R₂ during the iteration. Since Qim approaches zero, after several updates, Qi enters the region R2.
Step 2. Start with (2
When Q' E R2 and Q E Ti, the return with initial start (2, s) is always -. So during the iteration, Q2. will increase and approach -1. Eventually, Q2 will enter T2.
Step Start with s)
Similar to step 2, the return is always -1, and Q will approach -1. Since in R2 we have Qim <
1, , Q will cross the line I and enter R2 after several updates.
Step 4. Start with (2, m)
In this case, Qi E R3 and Q E T2, so every episode is generated by the same policy and is of the form:
2, m, 1, 8, 8, So the returns are i.i.d. random variables, and from lemma we have
E|G] -1 1-
(50)
Let be the number of episodes generated in this step and G; be their returns, then
Sn = Gi - G2 + + Gn
By the strong law of large numbers, have
S.
Pl, a.s. (as + +00)
(51)
n
Assume that we have had t iterations before start step 4, and there are L stored Return(2, m),
then
LQ + Sn LQ L+ L +
S.
Qtta
(52)
L +
since L and Qun finite numbers and independent of n, have
lim Qutm 111 a.s. n-000
(53)
Therefore, when we keep choosing (2,m) m) as the initial start and updating Q(2, m), we will have
Qth < --1++ à for some n. Thus, Q will enter the region Tg almost surely after several iterations. Note that even though the policy n. (2) changes after Q% crosses the line 12, it does not affect the return the generated episode with the initial state-action pair (2, m) since only the first state of the generated episode is state 2.
Step 5. Start with (1,s)
In this case, at first have
Qi > Qt and Q > Q%
(54)
therefore n. (1) stay and (2) stay. The generated episode with initial (1, is of the form:
1,8, 1, 8, 1,,,..
(55)
and the returns are i..dd. random variables with the expectation:
-1
1- =143
(56)
32

---

Published as a conference paper at ICLR 2022
Similar to the argument in step 4, when keep updating Qis by choosing (1, s) as the initial start, Qi's can not stay in R3 forever. will approach - -P3. So Q will cross the line 1 a.s.
After crossing the line 11, Qf will enter R2 I, where I is the region
I= {(Q)m Im 27+)) -b < Qum < -1, Qim > Qi Qi -22 + 8}
(57)
Q enters R2, we end this step and move to the next. Otherwise, we still keep updating Qi.- At this moment, we have
Qi < Qim and Q2 > Q2m
(58)
the generated episode then becomes
s, m, 2, 8, 8, s...
(59)
and the returns are i.i.d. random variables from another distribution with the expectation:
E|G
+ 7(1 = -22 =
(60)
'
so if Qi stays in I during the iteration, Qi, will approach =22- On the other hand, since we can successively get returns equal to -1, Qi might return to R3. Then the generated episodes are of type ( Qi will again cross the line l after several updates. We claim that Q can not oscillate between R3 and I forever. If so, we will get infinitely many sample returns with the expectation either 422 or -1a, the sample mean, Qi, will close to convex combination of -12 and -13- And we will have Qi. 422 + 8 for some Therefore, Qi enters R₂ after several updates eventually.
Step 6. Start with m1,
The possible episode in this case
1, 1, 2, 2,
therefore the expectation of the return is -111- During the iteration, Q will converge to -11. So Qim will decrease, and Q" will return to R1. Note that the sample return satisfies
G
1-7 7>17-7
7
(61)
When QT E R2, the value of Qut is at least - -b(b1 + -2g). By condition (3) and our assumptions 45 on bj and 8, we have
Q 42
(62)
Therefore, when QT E R2, + will not cross the line I during the iteration, and the policy n. does change. This ensures that can get returns from the same distribution so that QT will return to Ri.
Step Start with (2,s)
In this case, we have Qf E R1, and Q E Ta, so the possible episode is:
2, 2, 8, 2, 8...
The expected return is -33 Similar to the previous discussion, after several updates, Q3 will cross the line l2 and enter T4, eventually.
Step& Start with (2.
When Q E R2 and Q E T, the return of an episode starts with (2, m) is always O. So when we keep updating Q%... it will approach and Q" will return Tı.
After Q returns to Tı we back to step 1 and follow the eight-step exploring starts 5 again. We can see that during this process, all the state-action pairs can be chosen infinitely often, and the Q-values will continue to alternate between these regions and not converge. Also, the policy does converge. Therefore, Algorithm following the exploring starts (5) does not converge with probability 1.
33


Reviews:
[{"review_id": "oVsmt9kAsXH", "reviewer": "Reviewer_U5JN", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is written well; I enjoyed how it provides a thorough yet accessible introduction to the MCES algorithm and known results for it. The theoretical results are also clear and intuitive, as well as their proofs. I agree with the claim that the main advantage here compared to previous work is in using all states of the trajectory for the update, instead of only the first one.\n\nWith that said, this seems like a classic case where the simplicity and elegance of the theory is because it is indeed simple and easy to derive. The results are intuitive and not surprising since they are (in my opinion) almost trivial. Once you limit the environment to a DAG and are able to sample each state-action pair indefinitely, it seems obvious to expect to converge to the optimal policy. This follows from the basic dynamic programming concept where you begin from the last state and gradually update your value function to being optimal. Also, as the limited subclass of MDPs considered which are essentially DAGs, it feels like classic CS literature should have similar solutions so a literature survey in that area is advised. \n\nI think the contribution would have been more significant if, for instance, the indefinite initial state selection would have not been possible. In that case, you will not necessarily sample the terminal state or its neighbours and a probabilistic analysis would most likely be needed. Alternatively, if the rate of convergence would have been analyzed, we could understand how the sampling procedure affects convergence, which might help guide more efficient variants of the algorithm. \n\nLastly, two questions: I'm not sure that AlphaZero updates all states within a trajectory instead of just the initial one as claimed in the middle of p.2. A reference is missing there. Second, why do mujoco environments qualify as a feed-forward environment as claimed in the bottom of p.2? The walking tasks there are highly repetitive.", "summary_of_the_paper": "The paper studies the Monte-Carlo Exploring-Starts algorithm on MDPs where states are never re-visited and provides convergence results for such MDPs.", "summary_of_the_review": "To summarize, while I enjoyed reading the paper and its simplicity (which I appreciate in general), its contributions are correspondingly minor and not surprising. The combination of the highly restrictive realm of tabular MDPs in which states are never revisited, together with the strong assumption of ability to sample every state-action indefinitely, generate an easy problem that is not particularly hard or interesting to solve.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jX3PyCgHdj-", "reviewer": "Reviewer_Eew5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n    Presentation is mostly clear\n    A clear comparison to related works\n    An important theoretical contribution to the field.\n    Simple idea and proof.\n    Empirical results echo the claims to some extend.\n\nWeakness:\n   The assumption of the uniqueness of the policy is not presented in the theorem.\n   More discussion about the empirical results would be helpful. For example, Tsitsiklis's algorithm requires a uniformly sampling of the start state in order to guarantee convergence, but empirically it also works well with a different way to sample the start state. I would like to see how the authors think about it.\n   Some expressions can be improved:  the word \"iteration\" is not in the algorithm but is in the proof to refer to something in the algorithm.\n   Some typos: 1. Algorithm3 line 9, it should be Q_t(S_t, t, A_t), 2. when citing a paper by two authors, sometimes it lists two authors' names and sometimes it uses et al.\n    ", "summary_of_the_paper": "This paper proposed a proof of the Monte Carlo Exploring Starts algorithm given by Sutton and Barto (1998) for a class of MDPs.", "summary_of_the_review": "Overall I like this paper because of the strengths listed in the main review. There is some weakness but it doesn't weaken the main contribution of the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "iA-6S4rOkPf", "reviewer": "Reviewer_Fsd8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Main comments:\n\nOverall I really like this paper. To prove convergence of stochastic iterative algorithms, existing results rely on the properties of Bellman equation, and use either super-martingale convergence or ODE approach. This paper uses induction along with strong law of large numbers, resulting in a much simpler proof. This paper does seem to be of interest to the broader community of ICLR.\n\nOther comments/questions:\n\n1 There are several typos, such as (1) \"Corrolary 1\" should be replaced by \"Corollary 1\", (2) the sentence before Corollary 1, the \"snd\" should be replaced by \"and\". The authors should carefully go over the paper again to fix them.\n\n2 As for the numerical experiments, I am curious to see the convergence rate comparison between MCES and model-free Q-learning, which is probably the most popular value-based RL algorithm in the literature.\n\nSuggestions on future directions: Now that convergence is shown for tabular MCES algorithm, there are many interesting potential future directions for this line of research.\n\n1 Convergence rate. The convergence rate of strong law of large numbers has been established in the literature. While the induction technique can be used to show asymptotic convergence, it is not clear if it can be used to show the convergence rate. It is an interesting future direction to show the convergence rate of MCES and compare it to that of Q-learning.\n\n2 Function approximation. The next question is about extending the result to the function approximation setting. Q-learning with function approximation is an major theoretical open problem in RL because of the deadly triad. I am curious to see if one can show any theoretical guarantees on MCES with function approximation, or if it suffers from the same difficulty as Q-learning.\n\n-------------After Author Feedback-------------\n\nThank the authors for their feedback. I would like to keep my score and vote for acceptance.\n\n\n", "summary_of_the_paper": "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.", "summary_of_the_review": "This paper provides convergence guarantees of MCES algorithm under mild assumptions, hence resolving an important open problem in RL. I enjoy reading this paper and I think it has enough contribution to be published at ICLR.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FOjS6hZJyaJ", "reviewer": "Reviewer_joaK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n- The paper provides a novel convergence proof for MCES that relaxes the assumptions that have been previously employed for proving convergence of MCES\n- The proof, as the authors highlight, is simple and does not make use of hard mathematical/statistical tools\n\nCons:\n- The classes of MDP considered seem very constraining. Basically, it is required that (in the less restrictive case under the optimal policy) the states are never re-visited along one trajectory. The authors succeed in providing justifications for these assumptions, especially providing several realistic examples in which the assumptions are fulfilled. Nevertheless, I think that these assumptions are ensuring that within one episode a single (s,a)-pair will be updated at most once, significantly simplifying the analysis. My main concern is about the significance of these convergence results under such strong assumptions. To put it another way, is this analysis a step towards the understanding of MCES for general MDPs or just the analysis of a particular restricted case?\n\nMinor issues:\n- Pag 4: \"Maximizing (2) corresponds to the stochastic shortest path problem\". Is it true? I think that this holds only when the reward penalizes the steps needed to reach the goal state, not for general rewards.\n- Lemma 1: I think that some condition on the almost sure boundedness of the involved random variables is needed.\n- The ticks on the plot axis are too small\n- Algorithm 3, line 9: Q should have an additional argument t\n- Pag 1:  doesn’t -> does not\n- Pag 4:  isn’t -> is not", "summary_of_the_paper": "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.", "summary_of_the_review": "Overall, I think that the paper provides a novel contribution. However, given that the considered assumptions are, in my opinion, very restrictive, I have concerns about the significance of the theoretical results. For these reasons, I opt for a borderline score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the convergence of the Monte Carlo Exploring Start (MCES) algorithm, a basic method in RL. Although the method is very simple and known for a long time, the condition for its convergence is not completely understood.

One of the latest results is from almost 20 years ago (Tsitsiklis, "On the Convergence of Optimistic Policy Iteration," 2002). That paper shows the convergence of the method under some restrictive assumptions on how the algorithm operates. In particular, that result requires that only the action-value function of the initial state-action pair of an episode be updated, as opposed to all visited state-action pairs. What is not known is whether we can update the action-values of all state-action pairs observed in a trajectory.

It is notable that one of Tsitsiklis (2002) result requires a uniform selection of the initial state-action. But he also describes a modification of the algorithm that allows convergence with a non-uniform initial distribution (see page 66 of that paper, close to the end of Section 3 - Optimistic Policy Iteration Using Monte Carlo for Policy Evaluation).

On the other hand, this paper establishes the convergence of MCES with no assumption on how the algorithm works. In particular, the algorithm updates the action-value function for all state-action pairs observed in an episode. As long as all state-action pairs are visited infinitely often (and not necessarily from a uniform distribution), the convergence is established.

There is a catch, however. The paper requires some assumptions on the class of MDPs. In particular, it requires the environment to be either Stochastic Feed-Forward (SFF) (more restrictive) or Optimal Policy Feed-Forward (OPFF) (less restrictive). The OPFF assumption states that under any optimal policy, a state is never revisited within an episode.

The proof technique of this paper is different from the usual stochastic approximation method, and may be considered simpler.

We have two positive reviewers (with score of 8) and two slightly negative ones (with score of 5). The concern of negative reviewers is that the OPFF assumption is very restrictive. And given such an assumption on the class of MDPs, the proof becomes very simple. Moreover, it is not clear that the proof techniques developed in this work is a step toward analyzing MCES for more general MDPs.

My related concern is whether OPFF vs. Non-OPFF is a good way to characterize MDPs for which MCES with every-state update is convergent. Figure 3 in the paper shows the current state of knowledge in the analysis of variants of MCES. We know a problem with "No convergence" within the fourth quadrant (which is Non-OPFF).
Is the class of Non-OPFF a tight superset of the non-convergent ones?  Or is it a much larger superset? If it is tight, then OPFF is a good characterization of when MCES works or not. If it is not tight, OPFF may not be the right way to characterize the convergence of MCES.

All being said, I believe this paper positively contributes to our knowledge of a basic and fundamental RL algorithm. It does not fully resolve the convergence question, but it is indeed a progress. Whether OPFF characterization is going to be the right one or not remains to be seen in the future. I would act optimistically here and recommend acceptance of the paper.

I encourage the authors to incorporate the comments by the reviewers in updating their papers, including:
- fixing all the typos
- providing more examples of problems that are OPFF
- resolving the claim about alphaZero
- providing empirical comparison with Q-Learning
Decision: Accept (Poster)