Periodic agent-state based Q-learning for POMDPs

Summary

The paper proposes a new RL algorithm for POMDPs. The standard approach to convert the POMDP in a belief MDP is not possible in the RL setting, when there is no knowledge about the system model. The alternative is to use an agent-state which is a function of the observation history. Standard RL algorithms can be adapted to the agent-state to learn policies for POMDPs. However, these standard algorithms lead to stationary policies which might not be optimal, as the agent-state may not satisfy the Markov property. As a consequence, the authors propose a special form of nonstationary policies that may be better suited for non-Markovian agent-states.

Strengths

1. The paper has an interesting problem setting and describes well the limitations of stationary policies applied to non-Markovian agent-states. 2. The authors provide an extensive discussion of the related work.

Weaknesses

1. The proposed algorithm leads to a very limited class of policies. Having periodic policies might only help, because several policies mixed might lead to a better strategy than having only one deterministic policy. Apart from that, is there an inductive bias to repeat the policies? 2. Another weakness is, that the paper mainly discusses deterministic policies. It would be more interesting to increase the set of policies to stochastic policies. It could be that a single stochastic policy has the same effect on mixing the policies and therefore the periodic policy has no advantage. 3. The numerical experiments consider only small examples.

Questions

Have you considered other non-stationary approaches?

Rating

5

Confidence

2

Soundness

2

Presentation

2

Contribution

2

Limitations

The authors addressed the limitations adequately.

Summary

This work proposes a type of non-stationary policy for POMDPs that is periodic. The authors argue that typical agent states in partially observable RL do not satisfy the Markov property and illustrate why introducing non-stationarity can improve the optimal policy within the policy class (vs considering only stationary policies), even if this policy cannot achieve global optimality across all history-dependent policies. The claims are supported by several well chosen examples, rigorous theory, and numerical experiments. I'm happy to strongly recommend acceptance.

Strengths

**Originality**: To my knowledge, the proposal of periodic policies for POMDPs is novel (though I am unfamiliar with theoretical papers in this area). The authors do a good job of presenting the relevant prior literature and what contributions in the work at hand are novel. Since the work generalizes stationary policies (using a period of $L=1$), I appreciated the remarks on how previous theoretical results can be obtained using the new theorems in this work. **Quality**: The approach is rigorously supported by theory, and some numerical experiments. While I did not verify all the proofs, the theorems seem correct. Throughout the paper, the discussion presented by the authors was extremely insightful. **Clarity**: The paper is well written and the ideas are clearly communicated. While the writing can be technically dense, this should be expected of a work of this nature. I particularly commend the authors for the example in Figure 1, since it immediately conveys a number of important features of this work in a concise manner. **Significance**: While it is not surprising that performance in POMDPs can be improved by leveraging non-stationarity (in the absence of belief states), it can be challenging to implement non-stationarity due to the infinite parameter requirement the authors highlight. This work is an interesting proposal of how this can be done in principle with only finite parameters. While it may still not necessarily be practical, I think the ideas are nonetheless valuable.

Weaknesses

**Originality**: No weaknesses that are not already apparent. **Quality**: 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 following is a list of limitations. These are mostly stated clearly in the paper and I don't think they constitute reasons to reject. - Choosing an appropriate period $L$ is difficult. While it is shown that choosing $L = n!$ monotonically improves, large values of $L$ have large memory requirements. - For the above reason, I'm not sure this particular algorithm will see practical use. - The choice of behavioural policy is critical. - The framing of the problem is limited to deterministic Q-learning. It does not consider stochastic or policy gradient methods. **Clarity**: A couple of minor issues: - In the introductory example, explicitly writing the values of $J^*_{BD}$, $J^*_{SD}$ under $\gamma = 0.9$ would aid in the comparison with $J^*_L$. - In the numerical examples, is there an explanation for why $u_1$ is a better choice than $u_2$ and $u_3$? **Significance**: See prior comments on practicality.

Questions

(As mentioned above:) 1. Could you please comment on the relevance of the insights towards larger POMDPs, like those common in deep RL? 2. In the numerical examples, is there an explanation for why $u_1$ is a better choice than $u_2$ and $u_3$? 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?

Rating

8

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

Yes.

Summary

This paper presents the problem of learning a policy in a partially observable environment in a model-free way. The authors address this problem by proposing to learn a non-stationary periodic policy that can outperform stationary ones. This aspect is motivated by the fact that the policy can be constructed either using the last observation or a fixed set of last observations as a state, which in general do not satisfy the Markov property. An approach based on learning periodic policies using Q-learning is presented and convergence guarantees for this type of policies are presented under some assumptions. Finally, a numerical experiment validates the claims and the benefits of using the devised approach.

Strengths

The writing of the paper is clear. The authors consider the approach of learning periodic policies and are able to extend the convergence guarantees that hold under the stationary case also to periodic policies.

Weaknesses

I will highlight here some weaknesses of the presented approach. The authors claim in lines 71-73 that "a non-stationary deterministic agent-state based policy performs better than stationary deterministic agent-state based policies". This claim is reported here using only the results reported based on example 2, thus lacking a more formal characterization of the statement. As a second note, if we formally consider the set of non-stationary policies as containing the set of stationary ones, the results of the claim are always true since the set of non-stationary policies is more expressive and thus more powerful than the second set. Theorem 1 addresses the main challenge of the convergence analysis of PASQL that is the non-markovianity of the agent state. However the same challenge is already faced, under stationary policies (for ASQL), in [1]. Since the same result was also proved in [1], this reduces the contribution of the presented statement which seems to extend it to the set of periodic policies. It is not clear what in general the benefits of using periodic policies are and, even though the authors show some examples where they are effective, it is in general not easy to choose the right value of the period $L$. Nonetheless, as stated by the authors, an increase in $L$ does not necessarily reduce the sub-optimality of the policy. Its increase however leads to an increase in the complexity of finding a good estimate of the Q-function for each $l \in L$. Furthermore, no indication is given on the choice of the behavioral policies that lead to the convergence to good policies. [1] Erfan SeyedSalehi, Nima Akbarzadeh, Amit Sinha, and Aditya Mahajan. “Approximate information state based convergence analysis of recurrent Q-learning”. In: European conference on reinforcement learning. 2023.

Questions

It is not clear to me the point (ii) in line 80. In particular, what does it mean that "the set of all periodic deterministic agent-state based policies of period L is not monotonically increasing"? It is also not clear to me why periodic policies with period specified as in line 83 have monotonically increasing performance. It is not clear why the authors state that the main challenge in this setting is the absence of the Markov property of the agent state $[Z_t]_{t\ge 1}$, however Lemma 1 defines the process (including the agent state $\{Z_t\}$) as a Markov chain. Another questions is: how is Lemma 1 derived? Is it an assumption? The authors claim that previous results hold under a restrictive assumption on the learning rates but they do not state what these assumptions are. Since this aspect is claimed as an improvement over previous work, it would be useful to describe the previous assumptions. The convergence guarantees of PASQL hold under the assumption that the Markov chain is periodic. How difficult is this assumption in practice? Would in this case the period of the optimal policy coincide with the periodicity of the chain? Furthermore, in section 5, the authors claim that, differently from previous results which assume the irreducibility and the aperiodicity of the Markov chain, the current work assumes that the chain is periodic which is "a weaker assumption". I do not get why this assumption is weaker since it appears that the irreduciblity and aperiodicity assumption should also hold for each $l \in L$ as appears in Assumption 3 in the appendix. Could the authors clarify this aspect?

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

N/A

Summary

The paper introduces PASQL (Periodic Agent-State Based Q-Learning), a novel reinforcement learning approach tailored for Partially Observable Markov Decision Processes (POMDPs). Traditional methods often rely on transforming POMDPs into fully observable MDPs by employing belief states. However, belief states require system model knowledge, limiting their practicality in model-free settings like RL. PASQL addresses this by learning non-stationary, periodic policies using agent states—compressed representations of history—which do not assume the Markov property. This method leverages periodic Markov chains and stochastic approximation theories to prove that PASQL converges to a cyclic limit and can outperform traditional stationary policies in terms of approximation error.

Strengths

1. PASQL creatively combines concepts from periodic Markov processes and Q-learning to handle non-Markovian dynamics, a significant departure from traditional RL methods. 2. The paper provides a rigorous theoretical framework, including convergence proofs and bounds on sub-optimality, which substantiates the claims made about PASQL's efficacy. 3. Through numerical experiments, the paper effectively demonstrates that PASQL can outperform standard Q-learning in POMDP settings, offering practical relevance to the theoretical claims. 4. The paper offers a comprehensive comparison with existing methods, highlighting PASQL’s advantages in handling agent states that do not satisfy the Markov property.

Weaknesses

1. The introduction of periodic policies increases complexity and may require more computational resources, which could limit practical applications. 2. The current study focuses on tabular representations, which might not scale well to high-dimensional problems or those requiring function approximation.

Questions

1. How does PASQL scale with the dimensionality of the state and action spaces in practical scenarios? 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?

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

yes