On the Convergence of Monte Carlo UCB for Random-Length Episodic MDPs

One of the most fundamental results in tabular reinforcement learning is that the Q-function estimator for Q-learning converges almost surely to the optimal Q-function, without any restriction on the environment. This classic result was originally proved for infinite-horizon discounted MDPs, for which the the optimal policy is both stationary and deterministic (Tsitsiklis 1994; Jaakkola, Jordan, and Singh 1994). Q-learning is based on dynamic programming and uses back-ups to update the estimates of the optimal action-value function.

Besides Q-learning, another major class of reinforcement learning algorithms is Monte Carlo (MC) algorithms (Sutton and Barto 1998), which are often employed for episodic MDPs. With MC algorithms, an optimal policy is sought by repeatedly running episodes and recording the episodic returns. After each episode, the estimate for the optimal Q function is updated using the episodic return. Then a new episode is generated using the most recent estimate of the Q-function. In contrast with Q-learning, pure MC algorithms do not employ backups.

For many natural episodic problems, such as games like Go and Chess and robotic tasks, the episode ends when a terminal state is reached. The episode therefore is of random length. For episodic environments with random length episodes, the natural optimization criterion is to maximize the (expected) total return until the episode ends. For this class of problems, it is well known in the MDP literature that there is an optimal policy that is both stationary (does not depend on the time index) and deterministic.

As with Q-learning, it is important to understand the convergence properties of Monte Carlo algorithms with random-length episodes. We note that MC algorithms are often used in practice. For example, training AlphaZero (Silver et al. 2018) employs Monte Carlo in both the inner loop (where Monte Carlo Tree Search (MCTS) is used) and in the outer loop, where a two-player MC episode is run until game termination, at which time estimates for the Q functions are updated. As it turns out, unlike Q-learning, MC algorithms are not guaranteed to converge. Indeed, counterexamples exist for non-convergence for an important class of MC algorithms (Bertsekas and Tsitsiklis 1996; Wang et al. 2022).

In this paper, we consider an important class of MC algorithms, namely, MC algorithms that use Upper-Confidence Bound (UCB) exploration at each state. As discussed in the related work, such algorithms have been studied extensively for the fixed horizon optimization criterion, for which the optimal policy is non-stationary. Here we explore MC-UCB algorithms for random-length episodes, which is often the more natural setup in practice. For such environments, although the optimal policy is stationary, we conjecture that MC-UCB does not always converge.

The main contribution of this paper is to establish almost sure convergence for MC-UCB for a very large and important class of environments, specifically, for environments whose states are never revisited when employing an optimal policy. (States may be revisited when employing a non-optimal policy). This class of MDPs includes stochastic MDPs such as blackjack and many gridworld environments with randomness (for example, due to wind). It also includes all deterministic environments and all episodic environments with a monotonically changing value in the state. The proof is based on induction and a probabilistic argument invoking the strong law of large numbers.

A second contribution of this paper is an extensive numerical study of MC-UCB. These results show that in two classic episodic environments, MC-UCB can achieve competitive performance and converge in both the policy and the value-function, when compared to an ideal but less practical exploration scheme where each episode is initialized with a random state-action pair.

RL typically aims to find the optimal policy for a Markov Decision Process (MDP). A finite MDP can be represented by a tuple $\{{\mathcal{S}},{\mathcal{A}},r,P\}$, where ${\mathcal{S}}$ is the finite state space; ${\mathcal{A}}$ is the finite action space; $r$ is the reward function from ${\mathcal{S}}\times{\mathcal{A}}$ to the reals; and $P$ is the dynamics function where for any $s\in{\mathcal{S}}$ and $a\in{\mathcal{A}}$, $P(\cdot|s,a)$ gives a probability distribution over the state space ${\mathcal{S}}$. We denote $\pi$ for the policy. In general a policy may depend on the current state, the current time and the entire past history. Denote $s_{t}^{\pi}$ and $a_{t}^{\pi}$ for the state and action at time $t$ under policy $\pi$, respectively.

We assume that the state space has a terminal state denoted by $\tilde{s}$. When the MDP enters state $\tilde{s}$, the MDP terminates. Let $T^{\pi}$ denote the time when the MDP enters $\tilde{s}$. $T^{\pi}$ is a random variable, and can be infinite if the MDP doesn’t reach the terminal state. The expected total reward when starting in state $s$ is

Similarly we define the action-value function as

Further denote

Let $\pi^{*}$ denote a policy that maximizes (1). We say that the MDP is episodic if under any optimal policy $\pi^{*}$, $P(T^{\pi^{*}}<\infty|s_{0}=s)=1$ for all $s$. Note that in this definition of an episodic MDP, episodes are of random-length. Maximizing (1) for an episodic MDP is sometimes referred to as the stochastic shortest path problem (for example, see (Bertsekas and Tsitsiklis 1991)). For the stochastic shortest path problem, there exists an optimal policy that is both stationary and deterministic, that is, a policy of the form $\pi^{*}:{\mathcal{S}}\rightarrow{\mathcal{A}}$.

Another popular optimization criterion is the finite-horizon criterion, where $T^{\pi}$ in (1) is replaced with a fixed deterministic value $h$. In this case rewards accumulate to time $h$ whether the MDP terminates or not. For finite horizon problems, optimal policies are typically not stationary; however, it can be shown that there exists an optimal policy that depends on the current state $s$ and the current time $t$ (Bertsekas and Tsitsiklis 1991).

An MDP is said to be Optimal Policy Feed-Forward (OPFF) if under any optimal policy a state is never revisited (Wang et al. 2022). Note that this definition allows for MDPs for which states are revisited under non-optimal policies. Many important MDPs are OPFF, including Blackjack (a stochastic environment), the environments examined at the end of this paper, and all deterministic environments.

In contrast with Monte Carlo methods, Q-learning is based on dynamic programming and uses back-ups to update the estimates of the optimal action-value function. For infinite-horizon discounted MDPs, Q-learning can be shown to converge with probability one to the optimal action-value function under general conditions, by putting Q-learning into the stochastic approximations framework (Tsitsiklis 1994; Jaakkola, Jordan, and Singh 1994). Moreover, for the stochastic shortest path problem (random-length episodes), it has been shown that the sequence of Q-learning iterates is bounded, implying the convergence of the action-value function (Yu and Bertsekas 2013). While the MC-UCB algorithm also aims to solve the stochastic shortest path problem, the proofs of convergence for Q-learning cannot be easily adapted for Monte Carlo algorithms. The MCES algorithm is related to the MC-UCB algorithm since both MCES and MC-UCB average Monte Carlo episodic returns to estimate the action-value function. However, the two algorithms employ very different exploration strategies. While MCES randomly chooses state-action pairs at the beginning of each episode, MC-UCB explores by adding UCB exploration to the current action-value estimate. In the general RL setting, the convergence of MCES is not guaranteed, since there exists a counterexample where MCES indeed does not converge to the optimal action-value function (Bertsekas and Tsitsiklis 1996; Wang et al. 2022). We conjecture that the MC-UCB algorithm also does not converge in general.

However, if the MCES algorithm is modified so that the Q-value estimates are updated at the same rate for all state-action pairs, and the discount factor is strictly less than one, then the convergence will be guaranteed. (Tsitsiklis 2002). Furthermore, by assuming that all policies are proper, it is shown via the stochastic approximations methodology that MCES also converges for undiscounted cases (discounted factor equal to one) (Chen 2018; Liu 2020). Recently, a new but simple approach (Wang et al. 2022) to this problem relaxes the assumption of a uniform update rate for all state-action pairs, providing almost sure convergence under the OPFF assumption, that is, a state is never re-visited within an episode under an optimal policy. In this paper we pursue this same strategy for the MC-UCB algorithm. However, we emphasize here that our proof is significantly more challenging than the proof in Wang et al. (2022) due to the nature MC-UCB algorithm.

There has been significant work on regret bounds for the finite-horizon MDP problems(Agarwal, Jiang, and Kakade 2019; Chang et al. 2005; Azar, Osband, and Munos 2017). When the horizon is finite, then the optimal policy is non-stationary. Furthermore, many problems of practical interest do not have a fixed-length horizon. We also note regret bounds typically only imply convergence in expectation, not almost sure convergence. Although regret bounds are important, we argue that it is first important to understand the convergence properties of the MC-UCB algorithm since convergence is not guaranteed as it is in finite-horizon problems.

We also note that the MC-UCB framework shares some similarities with the Monte Carlo Tree Search (MCTS) algorithms. According to Vodopivec, Samothrakis, and Šter (2017), the UCT algorithm (Kocsis and Szepesvári 2006), one of the fundamental MCTS algorithms, can be viewed as an offline on-policy every-visit MC control algorithm that uses the UCB1 (a variant of UCB, discussed in appendix A) as the policy. The MCTS algorithms can also be considered as finite-horizon since they truncate the complete game trajectories at a fixed length.

In this section, we return to the MC-UCB framework described in Section 2 and derive the almost sure convergence of both the action-value function and state-value function under the OPFF assumption.

Before we present the almost sure convergence proof for the OPFF setting, we note that OPFF environments allow the learning agent to revisit previous states for sub-optimal policies; therefore, the agent may get into an infinite loop where the terminal state is never reached. To address this issue, we set a time limit $M$ depending on the number of states in the MDP, as shown in Algorithm 2. If the length of an episode exceeds this limit, we terminate the algorithm (line 3). Additionally, there are some special corner cases where taking sub-optimal actions never yields a complete episode, such as actions leading to a self-loop. Although such actions do not prevent the convergence of the estimated state-value functions and the policy, they cause the Q estimates not to converge. In order to address this issue, we add lines 5 and 6 to the algorithm. Since the action-value function for optimal actions will be almost surely greater than that for sub-optimal actions, as we will show in the proof, we can generate a complete episode in those corner cases.

Note that one can modify MC-UCB to make all Q estimates converge even faster. For example, similar to the model-based method (Azar, Osband, and Munos 2017), one can estimate transition probabilities and V estimates, and then update Q estimates by the Bellman equation. In this case, our analytical methodology still applies. However, in order to follow the standard MC-UCB framework and to simplify the analysis in this paper, we use the approach mentioned above to deal with the theoretical convergence of all Q values. Finally, we use the first-visit mechanism (line 12) to calculate the average returns, since the every-visit mechanism may cause a slower convergence for tasks with cycles (Singh and Sutton 1996; Sutton and Barto 1998).

Let $V_{n}(s)=\frac{1}{n}\sum_{t=1}^{n}G_{t}^{s}$ be the estimated state-value function of state $s$ by averaging total $n$ returns $\{G^{s}_{t}\}_{t=1}^{n}$, where $G_{t}^{s}$ is the $t$-th return collected in state $s$; $Q_{n}(s,a)=\frac{1}{T^{s}_{a}(n)}\sum_{u=1}^{T^{s}_{a}(n)}G_{a,u}^{s}$ be the estimated action-value function, where $G_{u}^{s,a}$ is the $u$-th return collected in state $s$ by choosing action $a$; $T_{a}^{s}(n)$ be the number of selections of action $a$ in the state $s$ out of total $n$ visits of that state. Let $\{r_{u}(s,a)\}_{u=1}^{T^{k}_{a^{*}}(n)}$ be finite $i.i.d$ reward random variables following an unknown law with an unknown but finite mean $\bar{r}(s,a)$. We now present the main result:

Note that the convergence result for the estimated Q-value to the optimal action-value function (3) together with the inequality (4) imply that the induced policy $\pi_{Q}(s)=\operatorname*{arg\,max}_{a}Q_{n}(s,a)$ converges almost surely to an optimal policy (which is stationary and deterministic).

We also emphasize that the theorem implies almost sure convergence for all MDPs for the (fixed) finite-horizon criterion (in which case the optimal policy is non-stationary). Given a finite-horizon period ${\mathcal{H}}$ = {0, 1, …, h}, the policy $\pi(s,t)$, Q values $Q(s,a,t)$, and V values $V(s,t)$ are now time-dependent for $t\in{\mathcal{H}}$. In this case, one can consider the time $t$ as part of the state, making the state space ${\mathcal{S}}\times{\mathcal{H}}$. Since the time step always increases within an episode, the algorithm never revisits previous states. Therefore, all finite-horizon MDPs are OPFF, and Theorem 1 applies.

We now present additional numerical experiments comparing MC-UCB and MCES. We emphasize that this numerical study aims to bring a better understanding of our theoretical results. Note that, MCES uses a more ideal, but less practical exploration scheme: for each episode, the initial state-action pair has to be randomly sampled from the state-action space. While MC-UCB does not require this condition and can be applied to more practical tasks. To be more consistent with prior works, we follow Wang et al. (2022) and focus on two classic OPFF environments: Blackjack and Cliff-Walking.

We conclude this paper by outlining some possible directions for future research. We have established the almost sure convergence for the MC-UCB algorithm for OPFF environments. Earlier in Bertsekas and Tsitsiklis (1996) and Wang et al. (2022), it was shown that for some non-OPFF environments, the MCES algorithm does not converge. We conjecture that this is also the case for MC-UCB. Finding a counterexample remains an open question.

As a first step for understanding the properties of MC-UCB with random episode lengths, it is important to understand under what conditions it does and does not converge. As a second step, it would be of interest to establish tight regret bounds for MC-UCB with random episode lengths with the OPFF assumption.

It would also be interesting to extend the theory presented here to the MDP game context. For example, it would be of interest to study convergence in the context of 2-person 0-sum games for OPFF MDPs. This would allow us to move the theory in this paper a step closer toward a general convergence theory for AlphaZero (Silver et al. 2018).