1 Introduction↩︎

The goal of reinforcement learning (RL; [1]) is to enable an agent to autonomously learn to act optimally in an unknown environment. Most RL algorithms are based on principles from dynamic programming, and often involve estimating a value function. The optimal value function \(v_\star\) represents the remaining sum of rewards in each state under the optimal policy. Given \(v_\star\), the optimal action in any state can be found by a single-step look-ahead. This fundamental principle enables RL algorithms to solve challenging control problems, from playing games [2]–[4] to robotics [5], [6]. All these environments, like most that are relevant in practice, are either very large, such that the value function can only be approximated, or are partially observable. In both cases, the agent has to act with incomplete information about the environment’s state, encoded in a state feature. Despite considerable progress, existing theory for this problem is still very limited [7], [8]. In this work, we focus on reinforcement learning in partially observable environments with deterministic observations. This setting is also known as hard state aggregation. While an optimal policy generally requires a memory of past observations [9], we restrict ourselves to the problem of learning a reactive policy, i.e., one that does not depend on past features. This policy maps features to distributions over actions that we call options [10], as deterministic policies may perform arbitrarily worse than stochastic policies [11].

Consider the corridor environment, shown in 1. The optimal policy is to go right at every state, yielding a total sum of rewards of \(0\), which is preferable to the immediate termination with \(-1\) on the left. Suppose that the agent cannot distinguish between the states in the blue bubble ([fig:corridor-a]), making this environment partially observable. While this seems a trivial environment, classical value-based RL algorithms such as Q-learning [12] will fail if applied directly. The reason for this is that these methods try to approximate the optimal value function. However, the states underlying the blue feature have completely different values, hence the value of this feature is ambiguous. Existing theoretical results for this problem [13], [14] thus require \(q_\star\)-realizability, which means that the optimal value function should be constant inside each feature. In this paper, we show that this assumption is stronger than necessary in many cases, and that a slightly augmented version of Q-learning converges to the optimal reactive policy under a strictly weaker assumption: rewire-robustness.

Our key insight is that, despite state aggregation, there exists a value for the blue feature in [fig:corridor-a] that enables dynamic programming to work: the value of the entrance state, in this case \(v_\star(1)\). With this value, a look-ahead from \(x = 0\) will prefer to enter the corridor, and a look-ahead from a corridor state will similarly prefer to go to the right. We call environments in which each feature has a unique entrance state (or a unique distribution over entrance states) quasi-Markov. Similar to the value function in a Markov decision process (MDP), the entrance values in quasi-Markov environments can be efficiently computed by dynamic programming. In particular, Q-learning converges to these values if the behavior policy only samples a new option when the observed feature changes. We call this augmented algorithm Committed Q-learning (2). The “commitment” to an option when entering a feature is not restrictive, since the goal of Q-learning is to find a reactive policy that deterministically maps features to options, and all such policies are naturally “committed.”

Many environments are not quasi-Markov. For example, consider the green bubble in [fig:corridor-b]. Here, there are two different entrance states (\(x = 1\) and \(x = k - 1\)) with two different values. However, this environment is rewire-robust: if we change the connections into the corridor (for example, by switching the two entrance states), the optimal reactive policy is unaffected. We prove that any rewire-robust environment can be well approximated by a quasi-Markov environment and show that Committed Q-learning converges almost surely to the optimal reactive policy in all rewire-robust environments. We further show that this condition is strictly weaker than \(q_\star\)-realizability, which, to the best of our knowledge, is assumed in all prior work on this topic. Our convergence analysis is based on the recent extension of the Borkar-Meyn theorem [15] to Markovian noise by [16].

2 Preliminaries↩︎

We consider the problem of reinforcement learning in a finite episodic partially observable Markov decision process (POMDP) with deterministic observations. The state space is of the form \(\mathcal{X}' = \mathcal{X} \cup \{x^\bot\}\), where \(\mathcal{X}\) is a finite set and \(x^\bot\) is an absorbing terminal state. An episode begins at time \(t = 0\) in a state \(x_0 \in \mathcal{X}\) selected randomly according to the initial state distribution \(p_0 \in \Delta_{\mathcal{X}}\), such that \(\mathbb{P}\{x_0 = x\} = p_0(x)\). At each time \(t\) before termination, the environment is in a state \(x_t \in \mathcal{X}\), and the agent selects an action \(u_t\) from the finite action space \(\mathcal{U}\). The environment then transitions to the next state \(x_{t+1} \in \mathcal{X}'\) with probability \[\mathbb{P}\{x_{t + 1} = x' \mid x_t = x, u_t = u\} = (T'_u)_{x', x}\text{,}\] where \(T_u' \in \Delta_{\mathcal{X}'}^{\mathcal{X}'}\) is the extended transition kernel under action \(u\).¹ For nonterminal states \(x\) and \(x'\), this probability is given by \((T'_u)_{x', x} \doteq (T_u)_{x', x}\), where \(T_u \in [0, 1]^{\mathcal{X} \times \mathcal{X}}\) is the transition kernel of the environment. The termination probabilities are \((T'_u)_{x^\bot, x} \doteq 1 - \gamma_{x, u}\), where \(\gamma_{x, u} \doteq \sum_{x' \in \mathcal{X}}(T_u)_{x', x}\). Finally, the terminal state \(x^\bot\) is absorbing, and thus \((T'_u)_{x', x^\bot} = [x' = x^\bot]\), where \([\cdot]\) denotes the Iverson bracket.

A feature mapping (or observation function) \(\varphi: \mathcal{X}' \to \mathcal{Z}'\) maps states to a finite feature space \(\mathcal{Z}' = \mathcal{Z} \cup \{z^\bot\}\), where \(\varphi(x) = z^\bot\) if and only if \(x = x^\bot\). This mapping defines a partition of the state space as \(\mathcal{X} = \dot{\bigcup}_z \mathcal{X}_z\), where \(\mathcal{X}_z \doteq \{x \in \mathcal{X} \mid \varphi(x) = z\}\) for \(z \in \mathcal{Z}\). It is often convenient to write \(\varphi\) as a matrix \(\Phi \in \{0, 1\}^{\mathcal{Z} \times \mathcal{X}}\), where \(\Phi_{z, x} \doteq \varphi_z(x) \doteq [\varphi(x) = z]\). At time \(t\), the agent only observes the feature \(z_t \doteq \varphi(x_t)\), which makes this environment partially observable. Given a reward function \(r: \mathcal{Z}' \to \mathbb{R}\), with \(r(z^\bot) \doteq 0\) and a finite set of options \(\Omega \subset \Delta_{\mathcal{U}}\), we can define the value of a reactive policy \(\pi: \mathcal{Z} \to \Omega\) in a state \(x \in \mathcal{X}\) as the expected sum of rewards in an episode starting in \(x\): \[v_\pi(x) \doteq \mathbb{E}_\pi\biggl[\sum_{t=1}^H r(z_{t}) \bigm\vert x_0 = x\biggr]\text{,}\] where the notation \(\mathbb{E}_\pi\) (or \(\mathbb{P}_\pi\)) indicates that \(u_t \sim \pi(z_t)\), and where \(H\) is the (random) termination time. Our goal is to learn a policy \(\pi\) that maximizes \(J(\pi) \doteq p_0^\top v_\pi\).

2.0.0.1 Notation.

The following notation is used frequently throughout the article. The transition kernel under an option \(\omega \in \Omega\) is denoted as \(T_\omega \doteq \sum_{u \in \mathcal{U}} \omega(u) T_u\). Similarly, for \(x \in \mathcal{X}\) and \(\omega \in \Omega\), we write \(\gamma_{x, \omega} \doteq \sum_{x' \in \mathcal{X}}(T_\omega)_{x', x}\). Given a feature \(z \in \mathcal{Z}\), we define \(\Pi_z \doteq \operatorname{diag}{\varphi_z}\) and \(\Pi_z^\bot \doteq I - \Pi_z\). These are the projection matrices in \(\mathbb{R}^{\mathcal{X}}\) onto the subspace corresponding to states with feature \(z\) and onto the corresponding orthogonal subspace. Finally, an environment is denoted as \(\mathcal{E} = (\mathcal{M}, \varphi)\), where \(\mathcal{M} = (\{T_u\}, p_0, r)\) is the MDP underlying \(\mathcal{E}\).

3 Main results↩︎

The Committed Q-learning algorithm is shown in 2. Apart from the use of more general options instead of actions, the only change from the classical non-committed Q-learning algorithm is the if-statement in [ln:if]. This change makes sure that a new option is only sampled if the observed feature changes. The algorithm iteratively updates a variable \(Q \in \mathbb{R}^{\mathcal{Z}' \times \Omega}\). We denote the state of this variable at the beginning of the \(t\)^th iteration ([ln:loop]) as \(Q_t\). Our convergence result relies on the following assumptions.

This is a very common assumption in the analysis of episodic reinforcement learning and dynamic programming algorithms [17]–[19]. It ensures that the Bellman operator of the episodic MDP \(\mathcal{M}\) underlying the environment \(\mathcal{E}\) is a contraction, which is essential for our convergence result.

This assumption is clearly necessary for exploration.

This is a common assumption in the analysis of stochastic approximation algorithms of the form we study in this paper [16], [20]. In fact, the result of [16] upon which our convergence analysis is based allows us to use a slightly more general form of step size, \(\alpha_t = \frac{\tau_1}{(t + \tau_2)^\beta}\) with \(\beta \in (0.5, 1]\), if we make the additional assumption that the Markov chain \((\xi_t)\) described in 5 is aperiodic.

[ass:proper,ass:explore,ass:alpha] suffice to establish almost-sure convergence of the sequence of iterates \((Q_t)\) in 2 to a point \(Q_\star\). However, additional assumptions are needed to guarantee optimality of the greedy policy with respect to \(Q_\star\). To see why, consider the environment shown in 6 (p. ). The optimal policy moves right in state \(\mathtt{a}\) and up in state \(\mathtt{b}\). A greedy policy selects the action based on the value \(v_\star\) of the next feature. Writing \(z \doteq \varphi(\mathtt{c}) = \varphi(\mathtt{d})\), we thus need that \(v_\star(z) < 0\) (to go up in \(\mathtt{b}\)) as well as that \(v_\star(z) > v_\star(\mathtt{b})\) (to go right in \(\mathtt{a}\)). However, since \(v_\star(\mathtt{b}) = 0\), this is a contradiction. Thus, no single value \(v_\star(z)\) is satisfactory. (The same argument works for Q-values as well.) To avoid situations like this, it is typically assumed that the optimal value function is realizable by the feature mapping \(\varphi\) (e.g., [13], [14]). The formal definition of \(q_\star\)-realizability is the following.²

If \(\mathcal{E}\) is \(q_\star\)-realizable, then (non-committed) Q-learning converges to the optimal policy [14]. However, \(q_\star\)-realizability is a very strong assumption that excludes simple environments like the corridor ([fig:corridor-a]), for which we have already shown that an optimal greedy policy exists (see 1). In this work, we show that realizability is stronger than necessary, and that Committed Q-learning converges to the optimal reactive policy under the strictly weaker condition of rewire-robustness. We first state our main result, and then define rewire-robustness.

3.0.0.1 Rewire-robustness.

What is rewire-robustness? Consider the environment shown in [fig:rr-a]. There are two ways to enter into the aggregate feature: from state \(\mathtt{a}\) (leading to \(\mathtt{c}\)), and from state \(\mathtt{b}\) (leading to \(\mathtt{d}\)). A rewiring of an environment \(\mathcal{E}\) is a modified version of \(\mathcal{E}\) in which these ‘entrance dynamics’ are changed, but the transition kernel remains otherwise unperturbed. For example, the environment shown in [fig:rr-b] is a rewiring of [fig:rr-a]. A stochastic behavior policy \(\pi\) implicitly defines an ‘average entrance’ behavior for each feature. The \(\pi\)-rewiring of an environment replaces all entrances of a feature by this ‘average entrance.’ For example, if \(\pi\) has low probability of moving up in state \(\mathtt{a}\) but high probability of moving up in state \(\mathtt{b}\), then the \(\pi\)-rewiring of [fig:rr-a] might look like [fig:rr-c]. While the entrance distributions in a rewiring are restricted to be mixtures of the entrance distributions of the original environment, in a generalized rewiring, a feature may be entered in an arbitrary way. [fig:rr-d] shows a generalized rewiring of [fig:rr-a]. The formal definition of rewirings and rewire-robustness are as follows. (Quasi-Markov and \(\pi\)-rewire-robust environments will be defined in the following two sections.)

The conditions (i) – (iv) of 2 constrain how much the environment \(\bar{\mathcal{E}}\) can differ from \(\mathcal{E}\). Condition (i) ensures that, while the initial state distributions may be different, the “initial feature distributions” must match: \[\bar p_0(z) = \sum_{x \in \mathcal{X}_{z}} \bar p_0(x) = (\Phi \bar p_0)_z \stackrel{\tikz\node[inner ysep=0pt] {\tiny(i)};}{=} (\Phi p_0)_z = p_0(z).\] Similarly, condition (ii) ensures that \(\bar p(z' \mid x, u) = p(z' \mid x, u)\). Condition (iii) demands that the intra-feature dynamics are unchanged: if \(\varphi(x') = \varphi(x) \doteq z\), then \[(\bar T_u)_{x', x} = (\Pi_z \bar T_u \Pi_z)_{x', x} \stackrel{\tikz\node[inner ysep=0pt] {\tiny(iii)};}{=} (\Pi_z T_u \Pi_z)_{x', x} = (T_u)_{x', x}.\] Finally, condition (iv) requires the feature entrance distributions of \(\bar{\mathcal{E}}\) to be derived from \(\mathcal{E}\). A feature \(z\) can be entered either at the beginning of an episode, in which case the unnormalized entrance distribution over \(\mathcal{X}_z\) is \(\Pi_z p_0\), or it can be entered from a state \(x\) outside of feature \(z\), in which case the unnormalized entrance distribution is \((\Pi_z T_u \Pi_z^\bot)_{:, x}\). Thus, the entrance space \(\varsigma_z\) is the linear span of all possible entrance distributions into feature \(z\).

3.0.0.2 Numerical example.

To motivate the relevance of 1, we illustrate the performance of Committed Q-learning in the corridor environment of [fig:corridor-a]. The results are shown in 5. While non-committed Q-learning fails to make progress even with very short corridors, Committed Q-learning quickly converges to the optimal policy. In this experiment, the behavior policy at time \(t\) is \(\epsilon_t\)-greedy with respect to the Q-table \(Q_t\) , where \(\epsilon_t = \frac{a_{\epsilon}}{t + b_{\epsilon}}\) such that \(\epsilon_0 = 0.1\) and \(\epsilon_{1000} = 0.01\). Similarly, the step size is \(\alpha_t = \frac{a_{\alpha}}{t + b_{\alpha}}\) such that \(\alpha_0 = 0.1\) and \(\alpha_{1000} = 0.01\). For the code, see https://github.com/onnoeberhard/q-commit.

4 Quasi-Markov environments↩︎

We now formalize the intuition developed in 1 that the correct value to assign to a feature is the average value of the feature’s entrance states, and that this choice guarantees that the value is meaningful in a dynamic programming context. This observation is far from obvious. Indeed, in their original investigation of reactive policies under hard state aggregation, [11] propose that, given a policy \(\pi: \mathcal{Z} \to \Omega\), the feature-value function \(v: \mathcal{Z} \to \mathbb{R}\) should minimize the value error \[\overline{\operatorname{VE}}(v) \doteq \mathbb{E}_\mu\bigl[\bigl\{v(z_t) - \mathbb{E}_\pi[R_t \mid x_t]\bigr\}^2\bigr]\text{,}\] where \(\mu\) is the stationary distribution of the policy \(\pi\) in the environment \(\mathcal{E}\), and \(R_t\) is the sum of future rewards. The function \(v\) that minimizes the value error is the \(\mu\)-weighted average of the values \(v_\pi(x)\) of all states \(x\) in a feature, where \(v_\pi\) is the value function of the MDP \(\mathcal{M}\) underlying \(\mathcal{E}\). To see why this is not adequate, consider again the corridor environment from [fig:corridor-a], but suppose the reward of state \(x = -1\) is \(r(-1) = 2\), such that it is optimal to terminate immediately on the left. Under the always-right policy \(\pi\), the stationary distribution is uniform in the corridor, and the values of the corridor states are \(v_\pi(x) = x\). Thus, the corridor value \(v_c\) that minimizes the value error is \(\frac{1}{k}\sum_{x = 1}^k v_\pi(x) = \frac{k + 1}{2}\), which is greater than \(2\) if the corridor length \(k\) is greater than \(3\), making the greedy policy suboptimal. Another common objective is the Bellman error \[\overline{\operatorname{BE}}(v) \doteq \mathbb{E}_\mu\bigl[\bigl\{v(z_t) - \mathbb{E}_\pi[r(z_{t + 1}) + v(z_{t + 1}) \mid x_t]\bigr\}^2\bigr].\] Under the always-right policy in the corridor, the Bellman error is minimized by \(v_c = k\) (4), which makes the greedy policy suboptimal for \(k > 2\). Both the value error and the Bellman error include a conditioning on the states of \(\mathcal{M}\) in their definitions, which leads to problems with learnability in the partially observable setting. This was first shown by [1], who demonstrate that it is not possible to estimate \(\overline{\operatorname{VE}}\) or \(\overline{\operatorname{BE}}\) from interaction with an environment. We thus propose the alternative definitions of value risk \[\mathcal{R}_{\mathrm V}(v) \doteq \mathbb{E}_\mu\bigl[\bigl\{v(z_t) - \mathbb{E}_\mu[R_t \mid z_t]\bigr\}^2\bigr]\] and Bellman risk \[\mathcal{R}_{\mathrm B}(v) \doteq \mathbb{E}_\mu\bigl[\bigl\{v(z_t) - \mathbb{E}_\mu[r(z_{t + 1}) + v(z_{t + 1}) \mid z_t]\bigr\}^2\bigr].\] These objectives do not have the same issues as \(\overline{\operatorname{VE}}\) or \(\overline{\operatorname{BE}}\) with learnability, as we show in 11. Furthermore, returning to the corridor example, while minimizing the value risk is equivalent to minimizing the value error (6), minimizing the Bellman risk yields the desired solution. To see this, note that we can minimize the Bellman risk \(\mathcal{R}_{\mathrm B}\) by solving the Bellman equation \[v(z) = \mathbb{E}_\mu[r(z_{t + 1}) + v(z_{t + 1}) \mid z_t = z]\] for \(v \in \mathbb{R}^{\mathcal{Z}}\). Solving for the value \(v_c\) of the corridor state under the always-right policy, we get \[v_c = \frac{k - 1}{k} (-1 + v_c) + \frac{1}{k} (k + 0) \implies v_c = 1\text{,}\] which is exactly the value of the corridor entrance state. In the rest of this section we prove that minimizing the Bellman risk will always result in a value function that satisfies this property, as long as the environment is quasi-Markov.

Thus, if an environment is quasi-Markov, then the state \(x \in \mathcal{X}_{z}\) will be distributed according to \(\sigma_{z}\) whenever the feature \(z\) is entered from the outside, independent of what the previous state was: if \(z \doteq \varphi(x_{t}) \neq \varphi(x_{t-1})\), then \[\begin{gather} \mathbb{P}\{x_{t} = x \mid x_{t-1} = x_-, u_{t-1}=u\}\\ = (\Pi_{z}\Sigma \Phi \bar T_{u}\Pi_{z}^\bot)_{x,x_-} = (\Pi_{z} \Sigma \zeta)_{x} = \zeta_{z} \sigma_{z}(x)\text{,} \end{gather}\] with \(\zeta \doteq (\Phi \bar T_{u}\Pi_{z}^\bot)_{:,x_-}\). This means that the Markov property holds whenever the feature changes: if \(z_{t - 1} \neq z_t\), then \(x_t \perp x_{t - 1} \mid z_t\). This property is also related to semi-Markov environments [10], [22], where the state \(x\) is similarly not revealed at every step. The equivalence to an entrance space dimension \(\leq 1\) is proved formally in 6; the intuition is given in the discussion from 3. If an environment is quasi-Markov, we can define an associated aggregate MDP as follows.

8 proves that the matrix inverse in the definition above is well-defined, as the spectral radius satisfies \(\rho(\Pi_z\bar T_\omega) < 1\). Note that the term ‘aggregate MDP’ is commonly used to describe systems of this type with general disaggregation matrices (e.g., [17, Sec. 6.5]). The ‘Bayesian’ disaggregation probabilities \(\{\psi_z^\omega\}\) that we define above correspond to the posterior distributions over states in a feature \(z\) under an option \(\omega\). To see this, note that when the feature \(z\) is entered, the initial distribution over states is \(\sigma_z\). After one transition under option \(\omega\), the probability mass on states in \(z\) is \(\Pi_z\bar T_\omega \sigma_z\). Continuing recursively like this, we see that the unnormalized stationary distribution comes from the Neumann series \[\sum_{\tau=0}^\infty (\Pi_z\bar T_\omega)^\tau \sigma_z = (I - \Pi_z \bar T_\omega)^{-1}\sigma_z = \tilde{\psi}_z^\omega\text{,}\] which converges as \(\rho(\Pi_z\bar T_\omega) < 1\) (e.g., [23] Theorem 4.11.2). In 5, we show that the transition kernel of \(\hat{\mathcal{M}}\) is closely related to our definition of the Bellman risk, as \((\hat{T}_\omega)_{z', z} = \mu(z' \mid z, \omega)\), where \(\mu\) is the stationary distribution of the behavior policy \(\pi\) in the quasi-Markov environment \(\bar{\mathcal{E}}\). Thus, the value function \(\hat{v}_\pi\) of the aggregate MDP is the minimum Bellman risk solution in \(\bar{\mathcal{E}}\). The following lemma shows that this solution will always satisfy the entrance value property described above.

The following result shows why the entrance value property is important: it implies that an optimal policy in \(\hat{\mathcal{M}}\) is an optimal reactive policy in \(\bar{\mathcal{E}}\).

5 Proof of 1↩︎

In this section, we use the theory of quasi-Markov environments developed above to prove 1. We focus on the convergence of 2 and on the implication (e), which characterizes the optimality of the policy \(\hat{\pi}_\star\). The remainder of 1 is straightforward and is discussed at the end of this section. The idea behind the proof is that, on average, the updates in 2 are sampled from \(\mu(z' \mid z, \omega)\), where \(\mu\) is the stationary distribution induced by the behavior policy \(\pi\). This distribution can be interpreted as the transition kernel of an aggregate MDP \(\hat{\mathcal{M}}_\pi\) corresponding to a specific quasi-Markov environment \(\bar{\mathcal{E}}_\pi\). We first prove that 2 converges to the optimal action-value function in \(\hat{\mathcal{M}}_\pi\). Then, 2 allows us to establish that \(\hat{\pi}_\star\) is optimal in \(\bar{\mathcal{E}}_\pi\). Finally, we use rewire-robustness to conclude that \(\hat{\pi}_\star\) is optimal in \(\mathcal{E}\).

Given an environment \(\mathcal{E}\), a behavior policy \(\pi\), and a sequence of step sizes \((\alpha_t)\), we define the random variables \(x_t\), \(\omega_t\), and \(Q_t\), for all \(t \in \mathbb{N}_0\), as the states of the variables \(x\), \(\omega\), and \(Q\) at the beginning of the \(t\)^th loop of 2 ([ln:loop]). We also define \(x_t'\) as the state of \(x\) immediately after [ln:step], and we write \(z_t \doteq \varphi(x_t)\) and \(z_t' \doteq \varphi(x_t')\). It can be verified by looking at 2 that the tuple \(\xi_t \doteq (x_t, \omega_t, x_t')\) is a Markov chain with transition kernel \[\begin{align} \mathbb{P}'\{\xi_t = (x, \omega, x') \mid \xi_{t - 1} = (x_-, \omega_-, x'_-)\}\\&= p(x \mid x'_-)\, p(\omega \mid x_-, \omega_-, x'_-, x)\, (T_\omega')_{x',x}\text{,}\end{align}\] where, writing \(z \doteq \varphi(x)\) (and similarly for \(z_-\) and \(z_-'\)), \[\begin{align} p(x \mid x'_-) &= \begin{cases} p_0(x) &\text{if } z'_- = z^\bot\\ [x = x'_-] &\text{otherwise, and} \end{cases}\\ p(\omega \mid x_-, \omega_-, x'_-, x) &= \begin{cases} \pi(\omega \mid z) &\text{if } z_-' \neq z_-\\ [\omega = \omega_-] &\text{otherwise.} \end{cases} \end{align}\]

Note that \(\mathbb{P}'\) is not the same as the transition kernel \(\mathbb{P}\) described in 2, in which a transition to \(x^\bot\) is absorbing, as [ln:restart] of 2 starts a new episode whenever the terminal state is reached. The Markov chain \((\xi_t)\) evolves in the set \(\Xi \subset \mathcal{X} \times \Omega \times \mathcal{X}'\) of reachable tuples \(\xi\). We first show that \((\xi_t)\) converges to a stationary distribution \(\mu \in \Delta_{\Xi}\).

Note that \(\mu(\xi) > 0\) for all \(\xi \in \Xi\). For convenience, we extend \(\mu\) to the space \(\Delta_{\mathcal{X} \times \Omega \times \mathcal{X}'}\) and define \(\mu(x, \omega, x') = 0\) for all \((x, \omega, x') \not\in \Xi\). In the following, we assume (without loss of generality) that all features are reachable under \(\pi\), and define \(\mu(z, \omega, z') \doteq \sum_{x \in \mathcal{X}_z}\sum_{x' \in \mathcal{X}_{z'}} \mu(x, \omega, x')\) for \(z, z' \in \mathcal{Z}\). We can now prove the convergence of 2 and characterize the solution \(Q_\star\). The partial observability in \(\mathcal{E}\) leads to correlated noise in the Q-learning updates of 2, which makes it difficult to apply standard stochastic approximation results that are typically used to analyze Q-learning. Our convergence result is instead based on the recent development by [16] which extends the Borkar-Meyn theorem to Markovian noise.

Thus, \(Q_\star\) is the optimal action-value function in an MDP on \(\mathcal{Z}\) with transition dynamics \(\mu\). We now show that this MDP can be interpreted as an aggregate MDP.

7 proves that \(\bar{\mathcal{E}}_\pi\) is a quasi-Markov rewiring of \(\mathcal{E}\) satisfying 1, such that \(\hat{\mathcal{M}}_\pi\) is well-defined. The entrance distribution \(\sigma_z\) is chosen to reflect the ‘average’ entrance distribution into \(z\) under the behavior policy \(\pi\). Consider again the environment shown in 6. Suppose the behavior policy \(\pi\) moves up with probability \(\delta\) and right with probability \(1 - \delta\) ([fig:nrr-b]). In this case, the green feature is entered at state \(\mathtt{c}\) with probability \(1 - \delta\) (from \(\mathtt{a}\)) and at state \(\mathtt d\) with probability \(\delta (1-\delta)\) (from \(\mathtt b\)). We thus see that the \(\pi\)-rewiring is given by [fig:nrr-c], where \(\eta \doteq 1 + \delta\) is the normalizing constant. Finally, the \(\pi\)-MDP is given by [fig:nrr-d], as the distribution over the states in the green feature of \(\bar{\mathcal{E}}_\pi\) is given by \(\psi(\mathtt c) = 1/\eta\) and \(\psi(\mathtt d) = \delta/\eta\). The following lemma provides the bridge between our convergence result (4) and the quasi-Markov theory developed in 4.

Thus, 2 is in fact the Bellman optimality equation of the \(\pi\)-MDP \(\hat{\mathcal{M}}_\pi\). This means that \(\hat{\pi}_\star\) is an optimal policy in \(\hat{\mathcal{M}}_\pi\), and, by 2, it is an optimal reactive policy in \(\bar{\mathcal{E}}_\pi\). To guarantee that \(\hat{\pi}_\star\) is also optimal in \(\mathcal{E}\), we need the following assumption.

Thus, we have proved (e) of 1. Note that if \(\hat{\pi}_\star\) is the unique minimizer of \(Q_\star\), then the inverse direction of (e) follows immediately, since \(\hat{\pi}_\star\) is the only optimal policy of \(\hat{\mathcal{M}}_\pi\) and, by 2, of \(\bar{\mathcal{E}}_\pi\). The implications (b) and (d) of 1 are trivial, since any rewiring is a generalized rewiring by definition, and we have shown that the \(\pi\)-rewiring is a rewiring (7). Implication (a) is proved in 7 and (c) is proved in 9. Furthermore (a) is strict, as the corridor environment ([fig:corridor-a]) is generalized rewire-robust, but not \(q_\star\)-realizable. Implications (b) and (c) are strict, as the environment shown in [fig:rr-a] is rewire-robust, but neither generalized rewire-robust, nor quasi-Markov. Finally, the strictness of (d) is proved in 10.

6 Related work↩︎

The concept of state aggregation goes back to the early days of dynamic programming [24] and has been a part of reinforcement learning since the field’s inception [25]. Soon after the initial convergence results for Q-learning based on stochastic approximation theory were established [18], [19], similar results were proved for reinforcement learning with state aggregation [11], [13], [26], [27]. More recently, the theory of state aggregation has been extended by several researchers [14], [28]–[30]. All these results either require \(q_\star\)-realizability to guarantee convergence to an optimal reactive policy, or they simply prove convergence of the algorithm without an interpretation of the solution. An assumption about the environment is likely necessary to enable an efficient algorithm, as [31] showed that the problem of finding a reactive optimal policy under state aggregation is NP-complete. To the best of our knowledge, the rewire-robustness that we propose is the weakest assumption under which convergence to the optimal reactive policy has been proved.

The aggregate MDP that we define in 4 is a classic tool for solving dynamic programming problems with state aggregation [17]. However, there is little discussion on how to choose the disaggregation probabilities \(\psi_z(x)\), since under \(q_\star\)-realizability, solving the aggregate MDP with any disaggregation matrix \(\Psi\) will yield the optimal value function. To the best of our knowledge, the work of [28] is the only study in which the disaggregation probabilities are chosen as in this paper, namely as the Bayesian posterior probabilities under the stationary distribution of \(\pi\). However, since [28] considers general environments, not quasi-Markov environments, the posterior probabilities \(\psi_z(x)\) depend on the policy \(\pi\) (and not just on the action inside feature \(z\) as for us). This makes it difficult to use this choice of disaggregation in practice, and indeed, while [28] studies the projected Bellman equation associated with this aggregate MDP, and shows that the Bayesian disaggregation matrix enables a better performance loss bound for value iteration, he does not propose a concrete algorithm for solving the projected Bellman equation. In fact, a few years later, [32] writes “It is not clear whether it is practically advantageous to select [\(\Psi\)] in the manner suggested by Van Roy.”

The corridor environment (1) is an augmented version of the T-maze [33], which is a classic example in the literature on partially observable RL [34], [35]. The T-maze is shown in [fig:tmaze-a]. The agent receives an observation of either ‘up’ or ‘down’ when entering the maze from the left. It then enters a corridor before reaching a decision point ‘?’, where the optimal action (up or down) is determined by the initial observation. In this environment, a reactive policy is clearly not sufficient, and a memory of past observations is needed. The optimal memory is \(z_t = (y_0, y_t)\), which contains the first and current observations. In [fig:tmaze-b], the POMDP representation of this environment is shown, and it can be seen that this choice of memory is a state aggregation of the underlying MDP. Furthermore, this environment is clearly rewire-robust, for the same reason as the corridor environment. Thus, given this memory mechanism, Committed Q-learning will find the optimal policy mapping memory to actions.

7 Conclusion↩︎

We have introduced Committed Q-learning, an algorithm which provably converges to the optimal reactive policy in POMDPs with deterministic observations under an intuitive rewire-robustness condition, which is strictly weaker than the common \(q_\star\)-realizability assumption. Along the way, we have introduced the concepts of Bellman risk and quasi-Markov environments, which are natural extensions of prior work, and are crucial for our analysis of Committed Q-learning. In a quasi-Markov environment, the Markov property holds between the features, since the state \(x\) is always independent of all previous states before entering the feature, but not inside a feature. While Committed Q-learning shares many similarities with regular Q-learning on the surface, in 5 we showed that the former effectively operates on a higher level: the \(\pi\)-MDP, whose state space is the feature space. This is reminiscent of the junction tree algorithm for inference in graphical models (e.g., [36, Sec. 9.6]), where efficient message passing operations are performed between cliques, while a brute-force computation is performed inside each clique. In our case, the brute-force computation is the maximization step in [ln:delta] of 2. We assume the existence of a finite set of options (distributions over actions) to optimize over. However, it is not clear how large such a set normally needs to be, as [37] proved that such an optimization is, in general, NP-hard.

There are several open avenues for future research. First, while we consider stochastic options instead of deterministic actions, [11] also showed that nonstationary options are preferable to stationary options. It would thus be interesting to see whether our theory can be extended to temporally extended options [10]. This is a natural extension, since our algorithm already commits to a single option that is kept until a feature is exited. Optimizing over nonstationary options is an open-loop reinforcement learning problem [38]. Another interesting direction would be to extend our result to other types of RL problems than the episodic environments (stochastic shortest path problems) that we consider here. We expect that the analysis transfers with minor modification to discounted infinite-horizon problems, but it is less clear if it also extends to the average reward setting. Finally, while the rewire-robustness assumption is weaker than \(q_\star\)-realizability, it is less clear how to extend this theory to cases where the assumption approximately holds. In previous results on state aggregation [13], [28], [30], the performance degrades with the approximation error on \(q_\star\). It would be important to understand if there is a natural definition of ‘approximate’ rewire-robustness under which a similar line of analysis can be established.

Acknowledgments↩︎

We thank the International Max Planck Research School for Intelligent Systems (IMPRS-IS) for their support. C. Vernade is funded by the Deutsch Forschungsgemeinschaft (DFG, German Research Foundation) under both the project 468806714 of the Emmy Noether Programme and under Germany’s Excellence Strategy – EXC number 2064/1 – Project number 390727645, and also gratefully acknowledges funding from the European Union (ERC grant ConSequentIAL, number 101165883). M.Muehlebach is funded by the DFG under the project 456587626 of the Emmy Noether Programme. Views and opinions expressed are those of the authors only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.

Impact statement↩︎

This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.

Contents↩︎

[1.5em]

8 Auxiliary results↩︎

9 Technical lemmas↩︎

10 Proofs↩︎

In this section we present all proofs that are omitted in the main text.

10.0.0.1 3.

Let \(\mathcal{E}\) be an environment and \(\pi\) a behavior policy such that 1 2 hold. Then, the Markov chain \((\xi_t) \subset \Xi\) is irreducible and has a unique stationary distribution \(\mu \in \Delta_\Xi\) satisfying \[\mu(x, \omega, x') = \mu(x, \omega)(T_\omega')_{x',x}\] for all \((x, \omega, x') \in \Xi\). Furthermore, this distribution satisfies, for all \(z \in \mathcal{Z}\) and \(\omega \in \Omega\), \[\begin{align} \Pi_z\mu_\omega &= (1 - \gamma_\pi)\pi(\omega \mid z)\Pi_z p_0 + \Pi_z T_\omega \Pi_z \mu_\omega\\ &+ \pi(\omega \mid z)\sum_{\omega' \in \Omega}\Pi_z T_{\omega'}\Pi_z^\bot\mu_{\omega'}\text{,} \end{align}\] where \(\mu_\omega \in \mathbb{R}^{\mathcal{X}}\) is defined as \(\mu_\omega(x) \doteq \mu(x, \omega)\), and where \(\gamma_\pi \doteq \sum_{x \in \mathcal{X}, \omega \in \Omega} \mu(x, \omega) \gamma_{x, \omega}\).

10.0.0.2 4.

Let \(\mathcal{E}\) be an environment and \(\pi\) a behavior policy such that 1 2 3 hold. Then, the iterates \(Q_t\) of 2 converge almost surely to a solution \(Q_\star\) satisfying \[Q_\star(z, \omega) = \mathbb{E}_\mu\bigl[r(z') + \max_{\omega' \in \Omega}Q_\star(z', \omega')\mid z, \omega\bigr]\text{.}\]

10.0.0.3 5.

Let \(\mathcal{E}\) be an environment and \(\pi\) a behavior policy such that 1 2 hold. Then, if \(\hat{\mathcal{M}}_\pi\) is the corresponding \(\pi\)-MDP with transition kernel \(\{\hat{T}_\omega\}\), \[\mu(z' \mid z, \omega) = (\hat{T}_\omega)_{z', z}\] for all \(z, z' \in \mathcal{Z}\), and all \(\omega \in \Omega\).

11 The Bellman risk is learnable↩︎

[1] show that the value error and Bellman error are not learnable, meaning that they cannot generally be estimated purely from observed quantities such as features and rewards. The proof constructs partially observable environments which cannot possibly be distinguished based on the observed features and rewards, but in which the value errors and Bellman errors do not coincide. While the value error at least has a unique minimizer, [1] show that the minimizer of the Bellman error can depend on these unobservable differences between environments. In this section, we show that this shortcoming does not apply to the value risk \(\mathcal{R}_\mathrm{V}\) or Bellman risk \(\mathcal{R}_\mathrm{B}\) defined in 4. The fundamental reason is that both \(\mathcal{R}_\mathrm{V}\) and \(\mathcal{R}_\mathrm{B}\) are defined purely based on observable quantities (rewards and features). In the following, we remove the assumption that \(\varphi\) is deterministic. We thus consider the general POMDP setting with stochastic observations \(z_t \sim \varphi(\cdot \mid x_t)\). Since these results are independent of the behavior policy, we simply let the environments be autonomous, meaning that there are fixed (latent) transition dynamics \(p(x_{t+1} \mid x_t)\). Following [1], we say that the data distributions of two autonomous environments coincide, if the distributions over feature sequences \(p(z_0, z_1, \dots)\) are the same. We assume that the reward is a deterministic function of the feature; this is without loss of generality, since the feature space could simply be extended to include the observed reward. In the following result, we assume that the state distributions of the autonomous environments converge to their stationary distributions.

Note that the above conclusion does not extend to the Value error \(\overline{\operatorname{VE}}\) and Bellman error \(\overline{\operatorname{BE}}\), as these are defined as expected values of the form \(\mathbb{E}_\mu[f(x_t)]\). The proof above also establishes that the value risk \(\mathcal{R}_\mathrm{V}\) and the Bellman risk \(\mathcal{R}_\mathrm{B}\) are “learnable” if the state distribution converges to the stationary distribution. An asymptotically unbiased estimate can be obtained by a simple estimator of the form \[\hat{\mathcal{R}}_t \doteq \frac{1}{t} \sum_{\tau = 1}^t f(z_\tau)\text{,}\] where \(f\) is chosen as above to reflect either \(\mathcal{R}_\mathrm{V}\) or \(\mathcal{R}_\mathrm{B}\). This estimator is furthermore simple to implement in a recursive fashion. The following result shows that the value error and the value risk are closely related.

12 On \(q_\star\)-realizability↩︎

We first show that our definition of \(q_\star\)-realizability (1) is the appropriate definition of linear \(q_\star\)-realizability for the case of hard state aggregation and stochastic shortest path problems that we consider. Note that in this case, the optimal action-value function is stationary: \(q^\star_{h_1} = q^\star_{h_2}\), for any \(h_1\) and \(h_2\). Furthermore, the feature mapping \(\varphi\) is a hard state aggregation. We can write this in the notation of [21] by defining the mapping \(\tilde{\varphi}: \mathcal{X} \times \mathcal{U} \to \mathbb{R}^d\), where \(d = |\mathcal{Z} \times \mathcal{U}|\), and \(\tilde{\varphi}(x, u)\) is the one-hot vector in \(\mathbb{R}^d\) corresponding to the tuple \((\varphi(x), u)\). Then, the function \(q: \mathcal{Z} \times \mathcal{U} \to \mathbb{R}\) in 1 is equivalent to the vector \(\theta^\star\) defined in Assumption 1 of [21], since \(\langle\tilde{\varphi}(x, u), \theta^\star\rangle = (\theta^\star)_{\varphi(x), u} = q(\varphi(x), u)\).

References↩︎

---

1. This denotes that \((T_u')_{:, x} \in \Delta_{\mathcal{X}'}\) for each \(x \in \mathcal{X}'\) and \(u \in \mathcal{U}\).↩︎

2. 12 compares 1 to [21].↩︎