Periodic agent-state based Q-learning for POMDPs

We thank the reviewer for the feedback.

1. Considering other non-stationary approaches

As we mention in the related work section, there are some other approaches to non-stationarity that have been taken in the literature e.g., continual learning and hierarchical learning including options. However, for the most part, the theoretical analysis is limited and when available is largely restricted to the MDP setting. Given the insights that are obtained from our current analysis, it may be possible to analyze some of these more general algorithms for POMDPs using the tools developed in our paper.

2. The numerical experiments consider only small examples.

The purpose of our numerical experiments is two-fold. First, to show that the convergence results do agree with what is predicted by the theory. Second, to show that PASQL can outperform ASQL. To make the first point, we need to restrict ourselves to simple models, as we have presented in the paper.

3. Deterministic vs stochastic policies.

Please see our response in the global rebuttal.

Thank you for your reply. We are not completely sure what you mean by "several policies mixed". Note that we have already shown via the example on line 959 (page 22) that periodic policies can do better than stochastic policies. So, we believe that you mean something other than stochastic policies.

Another interpretation of "mixed policies" is according to the terminology used in game theory. In this setting, the agent has a set of $m$ deterministic policies $(π_1, \dots, π_m)$. Before the system starts running, the agent picks a random variable $M$ in the set $\lbrace 1,\dots, m\rbrace$ with probability $(p_1, \dots, p_m)$ and then plays the policy $π_M$ forever. This is called a "mixed policy" in game theory and we will denote it by $μ$.

Let $J(π_i)$ denote the performance of policy $π_i$. Then, by linearity of expectation

$J(μ) = p_1 J(π_1) + \cdots + p_m J(π_m).$

In particular, this means that

$\displaystyle J(μ) \le \max_{i \in \lbrace 1, \dots, m\rbrace} J(π_i).$

Thus, mixing cannot improve performance.

In the above argument, there was no restriction on the class of policies. So, if we take a policy that mixes between stationary deterministic policies, then it cannot do better than the best stationary deterministic policy. So, a periodic deterministic policy will perform better than mixed policies that mix between stationary deterministic (or even stationary stochastic) policies.

Thank you for your comments and the positive endorsement. We address your questions and concerns below.

1. Could you please comment on the relevance of the insights towards larger POMDPs, like those common in deep RL?

The current state of the art $Q$-learning based deep RL algorithms for POMDPs always converge to a stationary policy. Our main insight is that non-stationary deterministic policies perform better than stationary deterministic and stochastic policies. As far as we are aware, none of the current deep RL algorithms for POMDPs exploit this insight. In this paper, we present a simple way to exploit this insight via periodic policies. We agree with your point that this introduces additional memory requirements, but as we argue in global response, the additional memory requirements are not too severe.

At the same time, for practical implementation of PASQL, one would leverage the insights of deep RL algorithms, especially when it comes to the choice of behavioral policy. The convergence of both AQSL (which is an idealized version of practical Q-learning based RL algorithms for POMDPs) and PASQL depends on the behavioral policy. However, practical algorithms such as R2D2 and dreamer use distributed actors, which help with exploration. Similar ideas can be used in practical implementation of PASQL.

2. In the numerical examples, is there an explanation for why $u_1$ is a better choice than $u_2$ and $u_3$ ?

It is difficult to provide an intuitive explanation for why policy $\mu_1$ is a better choice than $\mu_2$ or $\mu_3$. The main reason is that under policy $\mu_1$, the agent executes actions with positive reward (the blue and the green arcs in Fig. 2) more often. The exact reason for this hard to explain verbally but we can "see" that easily via a Monte Carlo simulation.

In general, it is difficult to provide a good intuition behind what constitutes a good behavioral policy in PODMPs (this is also true for ASQL). We did perform some numerical experiments on small models where we computed the performance of all behavioral policies (by discretizing the behavioral policies, computing the converged policy $\pi_{\mu}$, and evaluating its performance via Monte Carlo). We found that in several models, there are behavioral policies that lead to a converged policy $\pi_{\mu}$ that is optimal, but they were not always intuitively obvious choices.

3. I can see why most agent states that aren't the belief state will not satisfy the Markov property. Could you elaborate on some other cases to help clarify this (in the paper)? For example, when the agent state is uninformative (e.g. constant), or when the agent state is an RNN encoding of the history, do these satisfy the Markov property?

To address this, we will adapt the paragraph starting on line 42 as follows:

When the agent state is an information state, i.e., satisfies the Markov property, i.e., $\mathbb{P}(z_{t+1} | z_{1:t}, a_{1:t}) = \mathbb{P}(z_{t+1} | z_t, a_t)$ and is sufficient for reward prediction, i.e., $\mathbb{E}[R_t | y_{1:t}, a_{1:t}] = \mathbb{E}[R_t | z_t, a_t]$, where $R_t$ is the per-step reward, $a_t$ is the action and $y_t$ is the observation, the optimal agent-state based policy can be obtained via a dynamic program (DP) [Sub+22]. An example of such an agent state is the belief state. But, in general, the agent state is not an information state. For example, frame stacking and RNN do not satisfy the Markov property, in general. It is also possible to have agent-states that satisfy the Markov property but are not sufficient for reward prediction (e.g., when the agent state is always a constant). In all such settings, the best agent-state policy cannot be obtained via a DP. Nonetheless, there has been considerable interest to use RL to find a good agent-state based policy ...

4. My only major concern is with the numerical experiments. First, the agent models used are rather weak (the agent only considers the current observation when deciding an action). Perhaps some stronger choices that would be more convincing are frame stacking or an approximation of the belief state with added noise.

The purpose of our numerical experiments is two-fold. First, to show that the convergence results do agree with what is predicted by the theory. Second, to show that PASQL can outperform ASQL. To make the first point, we need to restrict ourselves to simple models, as we have presented in the paper. In principle, we could have used more sophisticated agents (e.g., by using frame stacking), but we did not do so in the paper because it is more difficult to visualize the theoretical results in that case.

In general, the set of non-stationary policies is a superset of the set of stationary policies. So, one would expect the performance of the best non-stationary policies to be greater than or equal to the performance of the best stationary policy. We are interested in whether this relationship is strict or not. In MDPs, the relationship is an equality: it is well known that stationary policies perform as well as non-stationary ones. The same is true for POMDPs when using a belief-state. All RL algorithms for MDPs leverage this fact and only learn stationary policies. When these algorithms are adapted to POMDPs, one typically replaces the "state of an MDP" with an "agent-state for a POMDP". Our main point is that such a naive replacement is not sufficient and more drastic structural changes in the algorithms may be needed because, in general, non-stationary policies can strictly outperform stationary policies in PODMPs. We illustrate this by providing examples that disprove "stationary policies have the same performance as non-stationary policies".

We thank the reviewer for the feedback. We address your questions and concerns.

1. Monotonically increasing performance of periodic policies

We illustrate this via an example. Let $Π_L$ denote the set of all agent-state based policies with period $L$. Consider a policy $(π_1, π_2, π_1, π_2, \dots) \in Π_2$, where $π_1 \neq π_2$. This policy does not belong to $Π_3$ because the policy at time 1 ($π_1$) is not the same as the policy at time 4 ($π_2$). However, this policy does belong to $Π_4$ because any sequence that is periodic with period 2 is also periodic with period 4.

Since $Π_2 \not\subset Π_3$, the set of periodic policies is not monotonically increasing. However, if we take any integer sequence $\lbrace L_n \rbrace_{n\ge 1}$ that has the property that $L_n$ divides $L_{n+1}$, then the performance of the policies with period $L_n$ is monotonically increasing in $n$. The sequence $L_n = n!$ mentioned on line 83 is just one such sequence. We will adapt the discussion around line 83 to make this clear.

2. Non-Markov agent state $Z_t$

The standard analysis of Q-learning for MDPs relies on two facts: (i) the agent-state (which is just the state in MDPs) is a controlled Markov process and (ii) the Q-learning iteration is a stochastic approximation of the Bellman update. The first fact is needed in order to define a Bellman operator. In POMDPs, if the agent state is not a controlled Markov process, we cannot define a Bellman operator and therefore need a different technique to analyze the convergence of Q-learning.

Lemma 1 is different from the fact that agent state is a controlled Markov process. The controlled Markov property states that

$\def\PR{\mathbb{P}}\PR(z_{t+1}|z_{1:t},a_{1:t})=\PR(z_{t+1}|z_t,a_t)$.

while Lemma 1 states that

$\def\1{\PR(s_{t+1},z_{t+1},y_{t+1},a_{t+1}|s_{1:t},z_{1:t},y_{1:t},a_{1:t})}\1=\PR(s_{t+1},z_{t+1},y_{t+1},a_{t+1} |s_t,z_t,y_t,a_t).$

These two are different and the latter does not imply the former because the functions of Markov chains are not necessarily Markov.

Proof of Lemma 1: Lemma 1 is an immediate consequence of the law of total probability, which implies that

$\def\2{\phantom{\1}}\def\I{\mathbb{1}} \1=\PR(a_{t+1}|s_{1:t+1},z_{1:t+1},y_{1:t+1},a_{1:t})\PR(z_{t+1}|s_{1:t+1},z_{1:t},y_{1:t+1},a_{1:t})\PR(s_{t+1},y_{t+1}|s_{1:t}, z_{1:t},y_{1:t},a_{1:t})$

$\2=μ(a_{t+1}|z_{t+1}) \I\lbrace z_{t+1} = \phi(z_t, y_{t+1}, a_t) \rbrace \PR(s_{t+1},y_{t+1}| s_t, a_t)$

$\2=\PR(s_{t+1},z_{t+1},y_{t+1},a_{t+1} | s_{t}, z_{t}, y_{t}, a_{t})$.

3. Improvement over previous learning rates

We compare our assumptions on learning rates with those in the literature in App E. To re-iterate, the previous learning rates considered were of the form

$\displaystyle α_t(z, a) = \frac{\I\lbrace Z_t = z, A_t = a\rbrace}{1+\sum_{n=0}^t \I\lbrace Z_n = z, A_n = a\rbrace},$

whereas assumption 1 is weaker and only requires $\sum_{t \ge 1} α^\ell_t(z,a) = \infty$ and $\sum_{t \ge 1} (α^{\ell}_t(z,a))^2 < \infty$.

4. Periodic Markov chains and optimal policies

It is relatively easy to ensure that the Markov chain $\def\M{\lbrace S_t,Y_t,Z_t,A_t\rbrace_{t \ge 1}}\M$ is periodic simply by choosing a behavior policy that is periodic.

The periodicity of the converged policy $π_μ$ is the same as the periodicity of the MC $\M$. However, this is not related to the periodicity of the optimal policy. In fact, as shown in the example in the introduction, in general, the optimal policy need not be periodic.

5. Weaker assumption of irreducibility and aperiodicity in periodic MC

Let $P_t$ denote the transition probability of the Markov chain $\M$. The previous results are assuming that $P_t$ is time-homogeneous, say equal to $P$, and that $P$ is irreducible and aperiodic. We are assuming that $P_t$ is time-periodic, say equal to $(P^0, \dots, P^{L-1})$, and that $P^0 P^1 \cdots P^{L-1}$, $P^1 \cdots P^{L-1} P^0$, etc. are aperiodic and irreducible. Note that we are not assuming that $P^0, \dots, P^{L-1}$ are individually irreducibile and aperiodic. In fact, by construction, these matrices are periodic.

When $L=1$, the two assumptions are equal. For $L \neq 1$, if the previously assumption holds, then so does our assumption but our assumption does not imply the previous assumption. In that sense, our assumption is mathematically weaker than the previous assumption.

6. Comparison with [Sey+23]

We strongly disagree with this characterization. The key point that we emphasize in the paper is that non-stationary policies can perform better than stationary policies in POMDPs with an agent state. Previous papers that analyze convergence of Q-learning for POMDPs such as [Sey+23] do so under very restrictive assumptions which do not hold in the non-stationary setting. As mentioned in point 3 above, they impose a strong assumption on the learning rates. But more importantly, [Sey+23] assume that the MC $\M$ converges to a stationary limiting distribution. Under this assumption, Q-learning would converge to a stationary limit and therefore the greedy policy will be stationary. Removing this assumption is technically non-trivial, as there is no existing literature on time-periodic Markov chains (the existing literature is on "state-periodic" but time-homogeneous Markov chains). Please see App B.2, in particular Prop 2 and 3, which are both new. These results enable us to generalize stochastic approximation results to time-periodic Markov chains (Prop 4), which is then a key tool used in the convergence analysis presented in this paper. None of these results follow from the analysis presented in [Sey+23].

7. Claim regarding non-stationarity is confusing

Please see the official comment below.

Thank you for the positive endorsement. We address your questions and concerns.

1. How does PASQL scale with the dimensionality of the state and action spaces in practical scenarios?

In the paper, we have focused on the tabular setting to analyze the simplest form of the algorithm. In a practical scenario, one would use function approximation with deep neural networks. The current state of the art ASQL implementations like R2D2 use LSTMs which involve using a recurrent layer that stores an "internal state'' of the agent state which acts as some form of memory of the history and implementations like dreamer use recurrent state space models (RSSMs) which consists of a self-predictive model that can predict forward in a latent space similar to a sequential variational autoencoder. So, the natural approach to implement PASQL will be to use a similar architecture, with a shared RSSM or LSTM base and $L$-different heads for the different $Q^{\ell}$.

The scaling with respect to state and action spaces will remain similar to that of ASQL with a worst-case additional scaling factor of $L$. There are two ways in which we can think about scaling in this setting: memory and sample complexity. For memory, the RSSM/LSTM part would remain the same as in ASQL but we would need a larger replay buffer, because a sample in the replay buffer is now associated with a particular value $\ell$. For the sample complexity, in the worst-case, we would require $L$-times more samples, but in practice, the scaling is much better because each $Q^{\ell}$ is bootstrapped from $Q^{[[\ell + 1]]}$, which leads to improved sample efficiency. We can see this fact in the experiments included in the paper where PASQL (Fig 3) and ASQL (Fig 5) have roughly the same sample complexity.

2. On what basis were the specific periods chosen for the policies in the experiments, and how sensitive is PASQL's performance to these choices?

In general, one can view the period $L$ as a hyper-parameter. In our experiments, we only tried with $L=2$. The main point that we wanted to make was that PASQL can give a better performance than ASQL, and the experiment with $L=2$ demonstrates that; so we did not experiment with larger values of $L$.

It is difficult to give a precise characterization of the sensitivity of PASQL to the choice of $L$ mainly because the performance depends on the choice of behavioral policy and there is no obvious way to "lift" the behavioral policy for period $L$ to a behavioral policy for a larger period. In theory, as we argue on line 83, the performance of periodic policies with period $L \in \lbrace n! : n \in \mathbb{N} \rbrace$ increases monotonically. In fact, if we take any integer sequence $\lbrace L_n\rbrace_{n\ge1}$ that has the property that $L_n$ divides $L_{n+1}$, then the performance of the policies with period $L_n$ is monotonically increasing in $n$. We will adapt the discussion around line 83 to clarify this point.