Periodic agent-state based Q-learning for POMDPs
Authors: Amit Sinha
Matthieu Geist
Aditya Mahajan
Venue: NeurIPS 2024 poster (2024)
Keywords: POMDPs
RL
Q-learning
non-stationary policies
non-Markovian environments
Primary area: reinforcement_learning
TL;DR: Periodicity helps in agent-state based RL in POMDPs because agent-states are not Markov.

Abstract: The standard approach for Partially Observable Markov Decision Processes (POMDPs) is to convert them to a fully observed belief-state MDP. However, the belief state depends on the system model and is therefore not viable in reinforcement learning (RL) settings. A widely used alternative is to use an agent state, which is a model-free, recursively updateable function of the observation history. Examples include frame stacking and recurrent neural networks. Since the agent state is model-free, it is used to adapt standard RL algorithms to POMDPs. However, standard RL algorithms like Q-learning learn a stationary policy. Our main thesis that we illustrate via examples is that because the agent state does not satisfy the Markov property, non-stationary agent-state based policies can outperform stationary ones. To leverage this feature, we propose PASQL (periodic agent-state based Q-learning), which is a variant of agent-state-based Q-learning that learns periodic policies. By combining ideas from periodic Markov chains and stochastic approximation, we rigorously establish that PASQL converges to a cyclic limit and characterize the approximation error of the converged periodic policy. Finally, we present a numerical experiment to highlight the salient features of PASQL and demonstrate the benefit of learning periodic policies over stationary policies.

Periodic agent-state based Q-learning for POMDPs
Amit Sinha', Matthieu Geist", and Aditya Mahajan'
McGill University, Mila *Cohere
Abstract
The standard approach for Partially Observable Markov Decision Processes (POMDPs) is to convert them to fully observed belief-state MDP. However, the belief state depends on the system model and is therefore not viable in reinforcement learning (RL) settings. A widely used alternative is to use an agent state, which a model-free, recursively updateable function of the observation history. Examples include frame stacking and recurrent neural networks. Since the agent state model-free, is used to adapt standard RL algorithms to POMDPs. However, standard RL algorithms like Q-learning learn stationary policy. Our main thesis that we illustrate via examples is that because the agent state does not satisfy the Markov prop- erty, non-stationary agent-state based policies can outperform stationary ones. To leverage this feature, we propose PASQL. (periodic agent-state based Q-learning), which is a variant of agent-state-based Q-learning that learns periodic policies. By combining ideas from periodic Markov chains and stochastic approximation, we rigorously establish that PASQL converges cyclic limit and characterize the approximation error of the converged periodic policy. Finally, we present a numerical experiment to highlight the salient features of PASQL and demonstrate the benefit of learning periodic policies over stationary policies.
Introduction
Recent advances in reinforcement learning (RL) have successfully integrated algorithms with strong theoretical guarantees and deep learning to achieve significant successes [Mni+13; Sil+16]. How- ever, most RL theory is limited to models with perfect state observations [SB08; BT96]. Despite this, there is substantial empirical evidence showing that RL algorithms perform well in partially observed settings [Wie+07; Wie+10; Hau00; HS15; Gru+18; Kap+19; Haf+20; Haf+21]. Recently, there has been sigmificant advances in the theoretical understanding of different RL algorithms for POMDPs [Sub+22; KY22; Sey+23; DRZ22] but complete understanding is still lacking.
Planning in POMDPs. When the system model is known, the standard approach [Åst65; SS73; CKL94] is construct equivalent MDP with the belief state (which is the posterior distribution of the environment state given the history of observations and actions at the agent) as the information state. The belief state is policy independent and has homogeneoss dynamics, which enables the formulation of belief-state based dynamic program (DP). There is a rich literature which leverages the structure of the resulting DP propose efficient algorithms to solve POMDPs [SS73; CKL94; CLZ97; Cha07; Zha09; PGT+03; SS04; SVO5J. See [KWW22] for review. However, the belief state depends on the system model, so the belief-state based approach does not work for RL.
RL in POMDPs. An alternative approach for RL in POMDPs is to consider policies which depend on agent state {2th21 where Z, Z, which is recursively updateable compression of the history: the agent starts at an initial state 2q and recursively updates the agent state as some function of the current agent-state, next observation, and current action. A simple instance of agent-state is frame stacking, where window previous observations is used as state [WS94; Mni+13; KY22]. Another example is a recurrent neural network such LSTM GRU to compress the history of observations and actions into an agent state (Wie+07; Wie+ 10; HS15; Kap+19; Haf+20]. In
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

2
6
7
8
12
13
14
15
16
Figure 1: The cells indicate the state of the environment. Cells with the same background color have the same observation. The cells with thick red boundary correspond to elements of the set Do {mnn + 1)/2 + E [N, where the action 0 gives reward of +1 and moves the to the right, while the action gives reward -1 and resets the state to 1. The cells with a thin black boundary correspond elements of the set Dj = IN \ Do. where the action 1 gives the reward of +1 and moves the state to the right while the action O gives a reward of -1 and resets the state to 1. Discount factor 0.9.
fact, argued in [DVZ22: Lu+23] such an agent state present in most deep RL algorithms for POMDPs. We refer to such a representation as an "agent state" because it captures the agent's internal state that it uses for decision making.
When the agent state is an information state, i.c., satisfies the Markov property, i.c., P(Ze=1/z1a, d1a) P( 12,,, ae) and is sufficient for reward prediction, i.e., Ri (1.. d1:c] E[R, 2t, aq] (where yi is the observation, a, is the action, and Rg is the per-step reward), the optimal agent-state based policy can be obtained via dynamic program (DP) [Sub+22]. An example of such an agent state 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 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.
One of the most commonly used RL algorithms is off-policy Q-learning, which we call agent-state Q-learning (ASQL). In ASQL for POMDPs, the Q-learnin iteration is applied as if the agent state satisfied the Markov property even though does not. The agent starts with an initial Q2 a), acts according to a behavior policy μu, i.e., chooses a uuzz), and recursively updates
Qc+1lz,a)= ac(z,a) tc(2z a) Rs + max Qc(2+11, a))
(ASQL)
where 7 E [0, 1) the discount factor and the learning rates {at)121 are chosen such that ar(2, a) = 0 if (z, a) * az). The convergence of ASQL has been recently presented in (KY Sey+23] which show that under some technical assumptions, ASQL converges to limit. The policy determined by ASQL is the greedy policy w.r.t. this limit.
Limitation of Q-learning with agent state. The greedy policy determined by ASQL is stationary (i.e., uses the same control law at every time). In infinite horizon MDPs (and, therefore, also in POMDPs when using the belief state an agent state), stationary policies perform well as stationary policies. This is because the agent-state satisfies the Markov property. However, in ASQL the agent state generally does not satisfy the Markov property. Therefore, restricting attention to stationary policies may lead to a loss of optimality!
As illustration, consider the POMDP shown in Fig. 1, which is described in detail in App. A.2 as Ex. 2. Suppose the system starts in state 1. Since the dynamics are deterministic, the agent can infer the current state from the history of past actions and can take the action to increment the current state and receive a per-step reward of +1. Thus, the performance Júp of belief-state based policies is J 1/(1 - 7). Contrast this with the performance Jjp of deterministic agent-state base policies with agent state equal to current observation, which is given by J = (1+7 (11---11011122 In particular, for ? 0.9, J 10 which is larger than J 4.022.
- < J
We show that the gap between J and J can be reduced by considering non-stationary policies. Ex. 2 has deterministic dynamics, so the optimal policy can be implemented in open-loop via sequence of control actions {az h121, where a; = 1t E D1). This open-loop policy can be imple- mented via any information structure, including agent-state based policies. Thus, non-stationary deterministic agent-state based policy performs better than stationary deterministic agent-state based policies. A similar conclusion also holds for models with stochastic dynamies.
The main idea. Arbitrary non-stationary policies cannot be used in RI. because such policies have countably infinite number of parameters. In this paper, we consider simple class of non-stationary

---

policies with finite number of parameters: periodic policies. An agent-state based policy π (TT, .... said be periodic with period L n. Ne whenever t = t' (mod L).
To highlight the salient feature of periodic policies, we perform a brute force search over all deter- ministic periodic policies of period T., for I. = {1. (1.....) 10), in Ex. 2. Let Jī denote the optimal performance for policies of period L. The result is shown below (see App. A.2 for details):
L
2
3
4
5
6
7
8
9
10
J1 4.022
4.022
7.479
6. 68184
8.810
7.479
9.340
8.488
9.607
8.810
The above example highlights some salient features of periodic policies: (i) Periodic determinis- tic agent-state based policies may outperform stationary deterministic agent-state based policies. (ii) (J1 is not a monotonically increasing sequence. This is because II, the set of all peri- odic deterministic agent-state based policies of period I., is not monotonically increasing. (iii) If I divides M, then Jr I Jis- This is because I,, C M In other words, if we take any integer sequence {L, Juz1 that has the property that I., divides I,+1, then the performance of the poli- cies with period Ln is monotonically increasing in n. For example, periodic policies with period L {n! n E IN] will have monotonically increasing performance. (iv) In the above example, the set Do is chosen such that the optimal sequence of actions' is not periodic. Therefore, even though periodic policies can achieve a performance that is arbitrarily close the optimal belief-based poli- cies. they are not necessarily globally optimal (in the class of non non-stationary agent-state based poli- cies). Thus, the periodic deterministic policy class is a middle ground between the stationary deter- ministic and non-stationary policy classes and provides us a simple way of leveraging the benefits of non- stationariot while trading-off computational and memory complexity.
The main contributions of this paper are as follows.
1. Motivated by the fact that non-stationary agent-state based policies outperform stationary ones, we propose a variant of agent-state based Q-learning (ASQL) that learns periodic policies. We call this algorithm periodic agent-state based Q-learning (PASQL).
2. We rigorously establish that PASQL converges w.r.t. the limit is a periodic policy. Due to the non-Markovian nature of the agent-state, the limit (of the Q-function and the greedy policy) depends on the behavioral policy used during learning. We quantify the sub-optimality gap of the periodic policy learnt by PASQL.
cyclic limit. Therefore, the greedy policy
4. We present numerical experiments to illustrate the convergence results, highlight the salient fea- tures of PASQL, and show that the periodic policy learned by PASQL indeed performs better than stationary policies learned by ASQL.
2 Periodic agent-state based Q-learning (PASQL) with agent state
2.1 Model for POMDPs
POMDP is a stochastic dynamical system with state 8, E S, input or E A, and output y E Y, where we assume that all sets are finite. The system operates in discrete time with the dynamics given as follows: The initial state 81 ~ p and for any time E IN, we have
P( 81as Via, d1.)) = P(s++1 (1Be+1,Bee) Be+1 St, dz) = P( 81,, at)
where P is a probability transition matrix. In addition, at each time the system yields a reward R. = r(st, az). We will assume that R. E j0, Rmax). The discount factor is denoted by 7 E (0,1).
Let स (M,, ... action at time is given by at #e 11) The performance of policy मे is given by
. denote any (history dependent and possibly randomized) policy. Then the
Σ ((t, oz) $1 ~ mp]
j E ( (e
The objective is to find (history dependent and possibly randomized) policy मे to maximize J
Recall that the system dynamics deterministic, so optimal policy can be implemented in open loop.
3

---

Agent state for POMDPs. An agent-state is mrdel-free recursively updateable function of the history of observations and actions. In particular, let Z denote agent-state space. Then, the agent state process (21) E Z, starts with an initial value 20, and is then recursively computed as 2++1 ((2 Mt+1, (:) for pre-specified agent-state update function d.
We use π (, ......) to denote an agent-state based policy, i..., a policy where the action at time is given by ar (zt). ). An agent-state based policy is said to be stationary if for all and t', we have Te (a|z) = Te (a|=) for all (z, a) E Z x A. An agent-state based policy is said to be
periodic with period L if for all and t' such that t t' (mod L), we have (T(aaz) = (alz) for all (z, a) E e A.
2.2 PASQL: Periodic agent-state based Q-learning algorithm for POMDPs
We now present periodic variant of agent-state based Q-learning, which we abbreviate PASQL. PASQL is an online, off-policy learning algorithm in which the agent acts according to a behavior policy μ (Jz. (2...)).... which is a periodic (stochastic) agent-state based policy ju with period L.
Let [4] = (t mod L) and L = {0, 1,..., L - -.....,--.. of agent-state, action, and reward observed by the agent. In PASQL. the agent maintains an L-tuple of Q-functions (Q),
1}. Let (z1, 01, Rí, 22, 022 R2....) be a sample path
Qf-1), f 2 1. The ε-th component, E L, is updated at time steps when [t] = In partieular, we can write the update as
(2+1 (z) + az)(2,a) Re mymax a'EA
max Of ( - VEEL, (PASQL)
where the learning rate sequence (aaf....... at. )2? is chosen such that af(2,a) 0
aL + ([1], =e, de) and satisfies Assm. 1. PASQL differs from ASQL in two aspects: (i) The behavior policy μ is periodic. (ii) The update of the Q-function is periodic. When = 1, PASQL collapses to ASQL.
The standard convergence analysis of Q-learning for MDPs shows that the Q-function convergences to the unique solution of the MDP dynamic program (DP). The key challenge in characterizing the convergence of PASQL that the agent state (22 does not satisfy the Markov property. Therefore, a DP to find the best agent-state based policy does not exist. So, we cannot use the standard analysis to characterize the convergence of PASQL. In Sec. 2.3, we provide a complete characterization of the convergence of PASQL.
The quality of the converged solution depends on the expressiveness of the agent state. For example, if the agent state is not expressive (e.g., agent state is always constant), then even if PASQL con- verges to limit, the limit will be far from optimal. Therefore, is important quantify the degree of sub-optimality of the converged limit. We do so in Sec. 2.4.
2.3 Establishing the convergence of tabular PASQL
To characterize the convergence of tabular PASQL, we impose two assumptions which are standard for analysis of RL algorithms [JSJ94; BT96]. The first assumption is on the learning rates.
Assumption For all (E, z, a). the learning rates (af(z, a)}{ are measurable with respect the sigma-algebra generated by (#1,a, anz) and satisfy af a) 0f (e, 2, + ([I], ze, at). Moreover, Ee21 of (z, a) oo and Σr21 (af (2) < 0c, almost surely.
The second assumption is on the behavior policy μ. We first state an immediate property.
Lemma For any behavior policy p. the process (S.,, 72) is Markov. Therefore, the processes ((St, Za, At) and {(St, Y,, Z4, A2) are also Markov.
Assumption 2 The behavior policy μ is such that the Markov chain ((Se, Yr, Zi, Ar)]11 is time-
periodic with period L and converges to eyclic limiting distribution (Ch, (Sg...., Sp (L-1), where E(en) (4 y, 2, a) for all (L, a) (i.e., all (e, z, a) are visited infinitely often).
We use से denote history dependent policies and denote agent-state based policies. Timee-peridic Markov chains are a generalization of time homogeneous Markov chains. We refer the reader to App. B for an overview of time-periodie Markov chains and cyclic limiting distributions, including sufficient conditions for the existence of such distributions.

---

For the ease of notation, we will continue to use S/ to denote the marginal and conditional dis- tributions w.r.t. ç/- In particular, for marginals and so on; for conditionals, we use S (s|2,, a) to denote ( 2, a)/ (2, a) and so on. Note that (p 2, y, a) = (s, P) a). Thus, we have that ( 2, 0, - ( 1z).
use (y, 2, to denote Eses S y, 2, a)
Theorem Under Assms. and 2, the process {(Q...... ) converges to a limit (Qu.....QQ) -.-0%=11 a.s., where the limit is the unique fixed point of the DP for a periodic MDP:4
(2) = =r)(2,)) + E Pf(ee1z,,0) max QuttT (2',a',
ve V
EZx A
(1)
a'EA
2
where the periodic rewards (ra r 11 and dynamics (Pp...., P P are given by
(2(220) a) = 2rss 2), 11(2/12,0) = Eie P(y a) ()) (2)
(s.g")ESXY
See App. E for proof. Some salient features of the result are as follows:
In contrast to Q-leaniig for MDPs, the limiting value Q depends on the behavioral policy p. This dependence arises because the agent state Ze is not an information state and thus is not pelicy-independeent See [Wit75] for discussion on policy independence of information states. We can recover some existing results in the literature as special cases of Thm. 1. we take L 1, Thm. I recovers the convergence result for ASQL obtained in [Sey+23, Thm. 2]. In addition, if the agent state is sliding window memory, Thm. I recovers the convergence result obtained in [KY22, Thm. 4.1]. J. Note that the results of Thm. 1 for these special cases is more general because the previous results were derived under restrictive assumption on the learning rates.
The policy learned by PASQL is the periodic policy T = (ff T given by
(2) arg max (2, E aEA
(PASQL-policy)
Since PASQL learns a periodic policy, it circumvents the limitation of ASQL described the in- troduction. Thm. 1 addresses the main challenge in the convergence analysis of PASQL: the non- Markovian dynamics of {Ze J121 A natural follow-up question is: How good is the learnt pol- icy (PASQL-policy) compared to the optimal? We address this in the next section.
2.4 Characterizing the optimality-gan gap of the converged limit
History-dependeer policies and their value functions. Let ht = (y1:t. d1:--1) denote the history of observations and actions until time t. and let o;: he + zz denotes the map from histories to agent-states obtained by unrolling the memory update function ø, i.c., on (h1) = @(20. y1, an), where 20 is the initial agent state, og is dummy action used to initialize the process, a2(h2) ((a (h1), V2, 01), etc.
For any history dependent policy म -... where Ne: hy + at, let V. = EN 7 h1 denote the value function of policy # starting from history h, at time t.
Let V/t(h)) sup; (he) denote the optimal value function, where the supermum is over all history dependent policies. In Thm. 1, we have shown that PASQL converges to a limit. Let n = ( n, denote the history dependent policy corresponding to the periodic policy 1/. 1 given by (PASQL-policy). i.e., Ta == I (o.(h))) In this section, we present a bound on the sub-optimality gap (h+) - -V,"" -Ve)(
Integral probability metrics. Let 3 be convex and balanced subset of (measureable) real-valued functions on S. The integral probability metric (IPM) w.r.t. 3. denoted by dæ. is defined as follows: any probability measures ε and &2 on S, we have dz (E1, = sup I [dL; over, for any real-valued function jf on S. define P3 == inf > 0: f/p E 3) to be the Minkowski functional w.r.t. 3. Note that if for every positive p. f/p & 3. then Ps (f) co.
sdC, More-
4 *See App. C for an overview of periodic MDPs.
$/ is balanced means that for every f and scalar such that [a] S 1. we have of
5

---

Many commonly used metrics on probability spaces are IPMs. For example, (i) Total variation dis- tance for which 3 {span(f) f < 1), where sf = max f min is the span seminorm of f- In this case, P3 (J) = span(f) (ii) Wasserstein distance for which 3 (Tip(f) s 1}. where Lip(f) the Lipschítz constant of f. In this case, (z( = Lip(f). Other examples include Kan- torovich metric, bounded Lipschitz metric, and maximum mean discrepancy. See [Mā197; Sub+22] for more details.
Sub-optimality gap. Let T(t, 6) = {r 2:: [7] f). Furthermore, for any & E L and t, define
of sup sup
E E[ h7, ar]
Σ
(( (=((+,)
TET(C,)) hr.ar
9ES
of = sup sup d3 (P = hy, ar), ( = -l,, TET((.0) s
Then, we have the following sub sub-optimality gap for u. Theorem Let (2) = max 02 (2, Then,
sup (h,, - V. nh (h.) - (1 74) EEL
2
Σ
l++a + 1o Ml
Ps P (V
(3)
hy
See App. F for proof. The salient features of the sub-optimality gap of Thm. 2 are as follows.
We can recover some existing results as special cases of Thm. 2. When we take L 1, Thm. recovers the sub-optimality gap for ASQL obtained in [Sey+23, Thm. 3]. In addition, when the agent state is a sliding window memory, Thm. 2 is similar to the sub-optimality gap obtained in [KY22, Thm. 4. Note that the results Thm. 2 for these special cases is more general because the previous results were derived under a restrictive assumption on the learning rates.
The sub-optimality gap in Thm. 2 is on the sub-optimality w.r.t. the optimal history-dependent policy rather than the optimal non- stationat agent-state policy. Thus, it inherently depends on the quality of the agent state. Consequently, even if I - xo, the sub-optimality gap does not go zero
is not easy to characterize the sensitivity of the bound to the period L. In particular, increasing means changing behavioral policy μr, and therefore changing the converged limit (C2...., (4--) which impacts the right hand side of (3) in complicated way. So, it is not necessarily the case that increasing L reduces the sub-optimality gap. This is not surprising, as we have seen earlier in Ex. 2 presented in the introduction that even the performance of periodic agent-state based policies is not monotone in T..
3 Numerical experiments
0.5
In this section, we present a numerical example to highlight the salient fea- tures of our results. We use the follow- ing POMDP model.
3
6.5
6.5
Example Consider a POMDP with
5). S = (0, 5).. A = {0. 1). Y 1) and 7 = 0.9. The dynamics are
(a) Dynamics under action 0. (b) Dynamics under action 1.
as shown in Fig. 2. The observation is
Figure The model for Ex. 1, where states which have the same color give the same observation; the green edges give a reward of +1 and blue edges give a reward of +0.5.
0 in states {0, 1, 2} which are shaded
white and is 1 in states (3, 5, which are shaded gray. The transitions shown in green give a reward +1; those in in blue give a reward of +0.5; others give no reward.
We consider a family of models, denoted by M(p), E [0. 1], which are similar to Ex. except the controlled state transition matrix is pl + (1 - pp) where P iss the controlled state transition matrix of Ex. 1 shown in Fig. 2. In the results reported below, we use p = 0.01. The hyperparameters for the experiments are provided in App. H.
Convergence of PASQL with T= 2. We assume that the agent state Z, = Y, and take period I. = 2. We consider three behavioral policies: μ4 = (0h.1H)) & E K = (1,2,3), 3)., where /4{ (0, 1) -

---

143
340
109
500
123
220
11
1,1,0
O.C.U
122
320
100
racidd
sond
C H
1/
123
142
G,O.
G,C, U]
Heau7 1000
0,0.3
Mixi
136
De07 somof
150077 1992
catro Souet
sonof
2/10 0
9/001)
4/0
Zonel
sounch
suni
Q/C.111
0,0.0
Q,0.3
100
250
Saive?
180x7
75000
Figure 3: PASQL iterates for different behavioral policies (in blue) and the limit predicted by Thm. 1 (in red).
A((O, 13), l E {0, 1]. The policy ur is completely characterized by four numbers which we write in matrix form as: [ (OJ0), 11 (0)0;; (O p (0]1)]. With this notation, the three policies are given by μ1 = [0.2, 0.8; 0.8, 0.2) 122 [0.5, 0.5; 0.5, 0.5]. Ms = [0.8. 0.2; 0.2, 0.8].
For each behavioral policy Pk. l E K, run PASQL for 25 random seeds. The median + interquantile range of the iterates (Q) 42) as well as the theoretical limits Qu (2.0) (computed using Thm. 1) are shown in Fig. 3. The salient features of these results are as follows:
PASQL converges close to the theoretical limit predicted by Thm. 1.
As highlighted earlier, the limiting value 2h depends on the behavioral policy Mag-
When the aperiodic behavior policy μ12 used, the Markov chain {(S., Y,, Zz, 1:) is aperi- odic, and therefore the limiting distribution Çy and the corresponding Q-functions Q do not depend on l. This highlights the fact that we have to choose periodic behavioral policy to converge to a non-stationan stationary policy (PASQL-policy)..
Comparison of converged policies. Finally, we compute the pe- riodic greedy policy T.. = (# nz: m1 given by (PASQL-policy),
Table 1: Performance of converged periodic policies.
k E K, and compute its performance J via policy evaluation on the product space S x (see App. G). We also do brute force search over all L = 2 periodic deterministic agent-state policies to compute the optimal performance J over all such policies. The results, displayed in Table 1, illustrate the following:
J1 6.793
J 6.793
J
Ju
1.064
0.532
The greedy policy Tye depends on the behavioral policy. This is not surprising given the fact that the limiting value 2i depends on Pa-
The policy uhz achieves the optimal performance, whereas the policies THe and Thg do not per- form well. This highlights the importance of starting with good behavioral policy. See Sec. for a discussion on variants such as e-greedy.
Advantage of learning periodic policies. As stated in the in- troduction, the main motivation of PASQL is that it allows us to learn -tatsntaionary policies. To see why this is useful, we run ASQL (which is effectively PASQL with L = 1). We again con- sider three behavioral policies: fi,, k K == {1, 21, where Ax: (0, 1} + ( 11), where (using similar notation as for L 1= 2 case) já (.22 122 = [0.5 M3 := [0.8;
Table 2: Performance of converged stationary policies.
J 2.633
JELL
J
J
0.0
1.064
2.633
For each behavioral policy js. E K. run ASQL, for 25 random seeds. The results are shown in App. A.I. The performance of the greedy policies The and the performance of the best period
7

---

L = 1 deterministic agent-state-basee policy computed via brute force is shown in Table 2. The key implications are as follows:
As was the case for PASQL, the greedy policy Tă, depends on the behavioral policy. As men- tioned earlier, this is fundamental consequence of the fact that the agent state is not an informa- tion state. Adding (or removing) periodicity does not change this feature.
The best performance of ASQL is worse than the best performance of PASQL. This highlights the potential benefits of using periodicity. However, at the same time, if a bad behavioral policy is chosen (e.g., policy ps)), the performance of PASQL can be worse than that of ASQL for a nominal policy (e.g., policy Π2). This highlights that periodicity is not magic bullet and some care is needed to choose a good behavioral policy. Understanding what makes a good periodic behavioral policy is an unexplored area that needs investigation.
4
Related work
Policy search for agent state policies. There is a rich literature on planning with agent state-based policies that build on the policy evaluation formula presented in App. G. See [KWW22] for review. These approaches rely on the system model and cannot be used in the RL setting.
State abstractions for POMDPs related agent-state based policies. Some frameworks for state abstractions in POMDPs include predictive state representations (PSR) [RGT04; BSG11; HFP14; KJS15b; KJS15at JKS16], approximate bisimulation [CPP09; Cas+21], and approximate information states (AIS) [Sub+22] (which is used in our proof of Thm. 2). Although there are various RL algorithms based on such state abstractions, the key difference is that all these frameworks focus on stationary policies in the infinite horizon setting. Our key insight that non-stationaary/eerioiii policies improve performance is also applicable to these frameworks.
ASQL for POMDPs. As stated earlier, ASQL may be viewed as the special case of PASQL when = The convergence of the simplest version of ASQL was established in [SJJ94] for Z, = Y, under the assumption that the actions are chosen i.i.d. (and do not depend on z,). In [PP02] it was established that Q9 is the fixed point of (ASQL). but convergence of {Q:h22 to Qh was not established. The convergence of ASQL when the agent state is a finite window memory was established in [KY22]. These results were generalized to general agent-state models in [Sey+23]. The regret of an optimistic variant of ASQL was presented in [DVZ22]. However, all of these papers focus on stationary policies.
Our analysis is similar to the analysis of [KY22; Sey+23] with two key differences. First, their convergence results were derived under the assumption that the learning rates are the reciprocal of visitation counts. We relax this assumption to the standard learning rate conditions of Assm. I using ideas from stochastic approximation. Second, their analysis is restricted to stationary policies. We generalize the analysis to periodic policies using ideas from time- time-periodic Markov chains.
Qllearning for non-Markovian environments. As highlighted earlier, a key challenge in under- standing the convergence of PASQL is that the agent-state is not Markovian. The same conceptual difficulty arises in the analysis of Q-learing for non-Markovian environments [MH+18; Cha+24; DY24]. Consequently, our analysis has stylistic similarities with the analysis in [MH+18; Cha+24; DY24] but the technical assumptions and the modeling details are different. And more importantly, they restrict attention to stationary policies. Given our results, it may be worthwhile to explore if periodic policies can help in non-Markovian environments as well.
Continual learning and non-stationary MDPs. Non-stationarity is an important consideration in continual learning (see [Abe+24] and references therein). However, in these settings, the environ- ment is non-stationary. Our setting is different: the environment is stationary, but non-stationary policies help because the agent state is not Markov.
Hierarchical learning. The options framework [Pre00; SPS99; Die00; BHP17] hierarchical approach that learns temporal abstractions in MDPs and POMDPs. Due to temporal abstraction, the policy learned by the options framework non-stationary. The same is true for other hierarchical learning approaches proposed in [WS97; CSL,21; Vez+ 17]. In principle, PASQL, could be considered as form of temporal abstraction where time split into trajectories of length and then policy of length T. is learned. However, the theoretical analysis for options is mostly restricted to MDP setting
8

---

and the convergence guarantees for options in POMDPs are weaker [Ste+18; Qia+18; LVC18). Nonetheless, the algorithmic tools developed for options might be useful for PASQL as well.
Double Q-learning. The update equation of PASQL. are structurally similar to the update equations used in double Q-learning [Has VGS16]. However, the motivation and setrings are different: the motivation for Double Q-learning is to reduce overestimation bias in off-policy learning in MDPs, while the motivation for PASQL induce non-stationarity while learning in POMDPs. Therefore, the analysis of the two algorithms is very different. More importantly, the end goals differ: double Q-learning learns stationary policy while PASQL learns a periodic policy.
Use of non-stationarr/perrodll policies in MDPs is investigated in [SL12; LS15; Ber13] in the context of approximate dynamic programming (ADP). Their main result was to show that using non-stationary or periodic policies can improve the approximation error in ADP, Although these results use periodic policies, the setting of ADP in MDPs is very different from ours.
Discussion
Deterministic vs. stochastic policies. In this work, we restricted attention to periodic deterministic policies. principle, we could have also considered periodic stochastic policies. For stationary policies (i.e., when period is one), stochastic policies can outperform deterministic policies [S1J94] as illustrated by Ex. in App. A.3. However, we do not consider stochastic policies this work be- cause are interested in understanding Q-learning with agent-state and Q-learning results in de- terministic policy. There are two options to obtain stochastic policies: using regularization [GSP19] which changes the objective function; using policy gradient algorithms [Sut+99; BBO1], which are a different class of algorithms than Q-learning.
However, as illustrated in the motivating Ex. 2 presented in the introduction, non-stationary policies can do better than stationary stochastic policies as well. So, adding non- -otsstaiionartty via periodicity remains an interesting research direction when learning stochastic policies as well.
PASQL is special case of ASQL with state augmentation. In principle, PASQL could be consid- ered as a special case of ASQL with an augmented agent state 2, = (Z,, [t]) However, the conver- gence analysis of ASQL in [KY22; Sey+23] does not imply the convergence of PASQL because the results of Y22: Scy+23] are derived under the assumption that Markov chain ((S,. Y,, Z, Ar) hr21 irreducible and aperiodic, while we assume that the Markov chain is periodic. Due to our weaker assumption, we are able to establish convergence of PASQL to time-varying periodic policies.
Non-stationary policies memory augmentation. Non- stationarity is a fundamentally different concept than memory augmentation. As illustration, consider the T-shaped grid world (first considered in [BakO1]) shown in Fig. 4, which has corridor of length 2n. In App. A.4, we show that for this example, a stationary policy which uses a sliding window of past m observations and actions as the agent state needs memory of at least m > 2n to reach the goal state. In con- trast, periodic policy with period
G₁
S
3
2n
T
G2
2n cells
Figure 4: A T-shaped grid world. Agent starts at s, where it learns whether the goal state is G1 or G2. It has to go through the corridor (1...., 2n with- out knowing where it is, reach T and go up or down reach the goal state.
3 can reach the goal state for every This example shows that periodicity is a dif- ferent concept from memory augmentation and highlights the fact that mechanisms other than memory augmentation can achieve optimal behavior.
The analysis of this paper is applicable to general memory augmented policies, so we do not need to choose between memory augmentation and periodicity. Our main message that once the agent's memory is fixed based on practical considerations, adding periodicity could improve performance.
Choice of the period L. If the agent state Z, is good approximation to the belief state, then ASQL (or, equivalently, PASQL with L = 1) would converge to an approximately optimal policy. So, using PASQL a period L is useful when the agent state is not good approximation of the belief state.
As shown by Ex. the introduction, the performance of the best periodic policy does not increase monotonically with the period L. However, if we consider periods in the set [n! n N]. then the performance increases monotonically. However, PASQL does not necessarily converge to the best periodic policy. The quality of the converged policy (PASQL--olicy) depends on the behavior

---

policy The difficulty of finding a good behavioral policy increases with L. In addition, increasing the period increases the memory required to store the tuple .Q...... Q") and the number of samples needed to converge (because each component is updated only once every I. samples). Therefore, the choice of the period I. should be treated as a hyperparameter that needs be tuned.
Choice of the behavioral policy. The behavioral policy impacts the converged limit of PASQL, and consequently it impacts the periodic greedy policy that is learned. As we pointed out in the discussion after Thm. 1, this dependence is a fundamental consequence of using an agent state that is Markov and cannot be avoided. Therefore, behavioral policies that lead to convergence to good policies.
important to understand how to choose
Generalization to other variants. Our analysis is restricted to tabular off- off-policy Q-learning where fixed behavioral policy is followed. Our proof fundamentally depends on the fact that the behavioral policy induces cyclic limiting distribution Such condition is not satisfied in variants such as 6-greedy Q-learning and SARSA. Generalizing the technical proof cover these more practical algorithms (including function approximation) an important future direction.
the periodic Markov chain ((St. Y,, Zz, 42)
Acknowledgments
The work of AS and AM was supported part by a grant from Google's Institutional Research Program in collaboration with Mila. The numerical experiments were enabled in part by support provided by Calcul Québec and Compute Canada.
10

---

References
[Abe+24]
David Abel, André Barreto, Benjamin Van Roy, Doina Precup, Hado van Hasselt, and Satinder Singh. "A definition of continual reinforcement learning". In: Advances in Neural Information Processing Systems 36 (2024).
[Ast65]
K.J Aström. "Optimal Control of Markov Processes with Incomplete State Infor- mation". In: Journal of Mathematical Analysis and Applications 10.1 (Feb. 1965),
pp. 174-205. ISSN: 0022247X.
[BHP17]
Pierre-Luc Bacon, Jean Harb, and Doina Precup. "The option-critic architecture". In: Proceedings of the AAAI conference on artificial intelligence. Vol. 31. 2017.
[BakO1]
Bram Bakker. "Reinforcement Learning with Long Short-Term Memory". In: Ad- vances in Neural Information Processing Systems. Ed. by T. Dietterich, S. Becker, and Z. Ghahramani. Vol. 14. MIT Press, 2001. URL:
hewpeediiinnnnnunnp..eee.. neurips. cc htppppperfflleee ftt.sffalepppep..ee/emma 2001 wile//illlee// httla//paaar//.///////////////00 Paper .df.
[BBO1]
Jonathan Baxter and Peter I. Bartlet. "Infinite-horizon policy-gradient estimation". In: Journal of Artificial Intelligence Research 15 (2001), pp. 319-350.
[BMP12]
Albert Benveniste, Michel Métivier, and Pierre Priouret. Adaptive algorithms and stochastic approximations. Vol. 22. Springer Science & Business Media, 2012.
[BT%6]
Dimitri Bertsekas and John Tsitsiklis. Neuro-dynamic programming. Athena Scien- tific, 1996.
[Ber13]
Dimitri P Bertsekas. Abstract Dynamic Programming Athena Scientifie,201
[BP24]
Shalabh Bhatnagar and L.A. Prashanth. Personal communication. 2024.
[BSG11]
Byron Boots, Sajid M Siddiqi, and Geoffrey Gordon. "Closing the Seaming-planninn loop with predictive state representations". In: The International Journal of Robotics Research 30.7 (2011), pp. 954-966.
[Bor08]
Vivek S Borkar. Stochastic approximation: dynamical systems viewpoint. Hindustan Book Agency, 2008
[CLZ97]
Anthony Cassandra, Michael Littman, and Nevin L. Zhang. "Incremental pruning: A simple, fast, exact method for partially observable Markov decision processes". In: Uncertainry in Artificial Intelligence. 1997.
[CKL.94]
Anthony Cassandra, Leslie Pack Kaelbling, and Michael L. Littman. "Acting opti- mally in partially observable stochastic domains". In: AAAI Conference Artificial Intelligence. Vol. 94. 1994, pp. 1023-1028.
[Cas98]
Anthony Rocco Cassandra. "Exact and approximate algorithms for partially observable Markov decision processes". PhD thesis. Brown University, 1998.
[Cas+21]
Pablo Samuel Castro, Tyler Kastner, Prakash Panangaden, and Mark Rowland. "Mico: Improved representations via sampling- based state similarity for Markov decision pro- cesses". In: Advances in Neural Information Processing Systems 34 (2021), pp. 301 30126.
[CPP09]
Pablo Samuel Castro, Prakash Panangaden, and Doina Precup. "Equivalence Relations in Fully and Partially Observable Markov Decision Processes". In: International Joint Conference Artificial Intelligence. 2009, pp. 1653-1658.
[Cha+24]
Siddharth Chandak, Pratik Shah, Vivek Borkar, and Parth Dodhia. "Reinforcement learning in non Man-Maroovian environments". In: Systems & Control Letters 185 (2024),
p. 105751.
[CSL21] Elliot Chane-Sane Sane, Cordelia Schmid, and Ivan Laptev. "Goal-conditioned reinforce- ment learning with imagined subgoals". In: International Conference Machine Learning. PMLR. 2021, pp. 1430-1440.
[Cha07] Joseph Chang. Stochastic Processes. Unpublished. Availale at http:://tw:: stat. yale. edt.-pollaaddCourreeeee /tt.orrreeeee....pppgm101//////a Soprringoos///mmmoottt/aaaaaooop pdf. 2007.
[DY24]
Ali Devran Kera and Serdar Yüksel. "Q-Learning for Stochastic Control under Gen- eral Information Structures and Non-Markovian Environments". In: Transactions on Machine Learning Research (2024).

---

[Die00]
Thomas G Dietterich. "Hierarchical reinforcement learning with the MAXQ value function decomposition". In: Journal of Artificial Intelligence Research 13 (2000), pp. 227-303.
[DRZ22]
Shi Dong, Benjamin Van Roy, and Zhengyuan Zhou. "Simple Agent, Complex Envi- ronment: Efficient Reinforcement Learning with Agent States". In: Journal of Machine Learning Research 23.255 (2022), pp. 1-54.
[DVZ22]
Shi Dong. Benjamin Van Roy, and Zhengyuan Zhou, "Simple agent, complex envi- ronment: Efficient reinforcement learning with agent states". In: Journal of Machine Learning Research 23.255 (2022), pp. 1-54.
[Dur19]
Rick Durrett. Probability: Theory and Examples. Cambridge University Press, Apr. 2019. ISBN: 9781108473682. DOI: 10. 101101199997 1017/9781108591033
[GSP19]
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. "A theory of regularized markov decision processes". In: International Conference on Machine Learning. PMLR. 2019, pp. 2160-2169.
[Gru+18]
Audrunas Gruslys, Rémi Munos, Ivo Danihelka, Mare G. Bellemare, and Alex Graves. "The Reactor: A Sample-Effiiient Actor-Critic Architecture". In: Proceedings of the International Conference on Learning Representations (ICLR). 2018. URL: https:
// //arxiv. abrg/4bs/770.. 04651.
[Haf+20]
Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi. "Dream to Control: Learnngg Behaviors by Latent Imagination". In: International Conference on Learning Representations. 2020.
[Haf+21]
Danijar Hafner, Timothy P Lillicrap. Mohammad Norouzi, and Jimmy Ba. "Mastering Atari with Discrete World Models". In: International Conference Learning Repre- sentations. 2021.
[HFP14]
William Hamilton, Mahdi Milani Fard, and Joelle Pineau. "Efficient learning and plan- ning with compressed predictive states". In: The Journal of Machine Learning Re- search 15.1 (2014), pp. 3395-33 2395-3439.
[Han98]
Eric A. Hansen. "Solving POMDPs by searching in policy space". In: Uncertainty in Artificial Intelligence. Madison, Wisconsin, 1998, pp. 211-219. ISBN: 155860555X.
[Has10]
Hado Hasselt. "Double Q-learning". In: Advances in neural information processing systems 23 (2010).
[HS15]
Matthew Hausknecht and Peter Stone. "Deep recurrent Q-learning for partially observ- able MDPs". In: AAAI Fall Symposium Series. 2015.
[Hau97]
Milos Hauskrecht. "Planning and control in stochastic domains with imperfect infor- mation".. PhD thesis. Massachusetts Institute of Technology, 1997.
[Hau00]
Milos Hauskrecht. "Value-function approximations for partially observable Markov decision processes". In: Journal of artificial intelligence research 13 (2000), pp. 33- 94.
[JSJ94]
Tommi Jaakkola, Satinder Singh, and Michael Jordan. "Reinforcement Learning Al- gorithm for Partially Observable Markov Decision Problems". In: Advances in Neural Information Processing Systems. Vol. 7. MIT Press, 1994, pp. 345-352.
[JKS16]
Nan Jiang, Alex Kulesza, and Satinder P Singh. "Improving Predictive State Repre- sentations via Gradient Descent." " In: AAAI Conference on Artificial Intelligence. 2016, pp. 1709-1715.
[Kap+19] Steven Kapturowski. Georg Ostrovski. Will Dabney, John Quan, and Remi Munos. "Recurrent Experience Replay in Distributed Reinforcement Learning". In: Interna- tional Conference on Learning Representations. 2019.
[KY22]
Ali Devran Kara and Serdar Yüksel. "Convergence of Finite Memory Q Learning for POMDPs and Near Optimality of Learned Policies Under Filter Stability". In: Mathe- matics of Operations Research (Nov. 2022). ISSN: 1526-5471. DOI: 10. 1287 mooor.
2022. 1331.
[KWW22] Mykel Kochenderfer, Tim A Wheeler, and Kyle H Wray. Algorithms for decision making. MIT press, 2022.
[KSS15]]
Alex Kulesza, Nan Jiang, and Satinder Singh. "Low-rank spectral learning with weighted loss functions". In: Artificial Intelligence and Statistics. 2015, pp. 517-525.
12

---

[KJS15b] Alex Kulesza, Nan Jiang, and Satinder P Singh. "Spectral Learning of Predictive State Representations with Insufficient Statisties." " In: AAAI Conference on Artificial Intelli- gence. 2015, pp. 2715-2721.
[KY97]
Harold J. Kushner and G. George Yin. Stochastic Appraximatiinn Algorithmss and Ap- plications. Springer New York, 1997. DOI: 10. 10.1000/9778 11778-1--99---1 4-9-488999----88 2696-8.
[LVC18]
Tuyen P Le, Ngo Anh Vien, and TaeChoong Chung. "A deep hierarchical reinforce- ment learning algorithm in partially observable Markov decision processes". In: Ieee Access 6 (2018), pp. 49089-49102.
[LS15]
Boris Lesner and Bruno Scherrer. "Non-Stationary Approximate Modified Policy It- cration". In: Interaational Conference on Machine Learning. Vol. 37. Proceedings of Machine Learning Research. Lille, France: PMLR. July 2015, pp. 1567-1575.
[Lit96]
Michael Lederman Littman."" "Algorithms for sequential decision-making" PhD thesis. Brown University, 1996.
[Lu+23]
Xiuyuan Lu, Benjamin Van Roy, Vikranth Dwaracherla, Morteza Ibrahimi, Ian Os- band, Zheng Wen, et al. "Reinforcement learning, bit by bit". In: Foundations and Trends in Machine Learning 16.6 (2023), pp. 733-865.
[MH+18]
Sultan Javed Majeed, Marcus Hutter, et al. "On Q-learning Convergence for Non- Markov Decision Processes." In: IJCAI, Vol. 18. 2018, pp. 2546-2552.
[Mni+13]
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. "Playing atari with deep reinforce- ment learning". In: arXiv preprint arXiv: 3/2.5602 (2013).
[Mü197]
Alfred Müller. "Integral probability metrics and their generating classes of functions". In: Advances in Applied Probability 29.2 (1997), pp. 429-443.
[Nor98]
James R Norris. Markav chains. Cambridge University Press, 1998.
[PP02]
Theodore J. Perkins and Mark D. Pendrith. "On the Existence of Fixed Points for Q- Learning and Sarsa in Partially Observable Domains", In: International Conference on Machine Learning. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2002, pp. 490-497.
[PGT+03] Joelle Pineau, Geoff Gordon, Sebastian Thrun, et al. "Point-based value iteration: An anytime algorithm for POMDPs". In: International Joint Conference Artificial In- relligence. Vol. 3. 2003, pp. 1025-1032.
[Pla77]
Loren Kerry Platzman. "Finite Memory Estimation and Control of Finite Probabilistic Systems." PhD thesis. Massachusetts Institute of Technology, 1977.
[PB24]
L.A. Prashanth and Shalabh Bhatnagar. Gradient -baseddt- algorithms for zeroth-order optimization. Now publishers, 2024. URL: http / www cae iitm ac in pdf. Doina Precup. Temporal abstraction in reinforcement learning. University of Mas- sachusetts Amherst, 2000.
[Pre00]
[Qia+18]
Zhiqian Qiao, Katharina Muelling, John Dolan, Praveen Palanisamy, and Priyantha Mudalige. "Pomdp and hierarchical options mdp with continuous actions for au- tonomous driving at intersections". In: 2018 21st International Conference on Intel- ligent Transportation Systems (ITSC). IEEE. 2018, pp. 2377-2382.
[Rii65]
Jens Ove Riss. "Discounted Markov Programming in Periodic Process". In: Oper- ations Research 13.6 (Dec. 1965), pp. 920-929. ISSN: 1526-5463. DOI: 10. 1287 opre. 13.6 6.920.
[RM51]
Herbert Robbins and Sutton Monro. "A Stochastic Approximation Method". In: The Annals of Mathematical Statistics 22.3 (1951), pp. 400
[RGTO4]
Matthew Rosencrantz, Geoff Gordon, and Sebastian Thrun. "Learning low dimensional predictive representations". In: International Conference on Machine Learning. 2004. Bruno Scherrer. On Periodic Markov Decision Processes. European Workshop on Re- inforcement Learning. Dec. 2016. URL: https : / /wwll.rl..... files. wordpress com/ 2016/12/ htt//shhere... .ddf.
[Sch16]
[SL12]
Bruno Scherrer and Boris Lesner. "On the use of non-stationary policies for station- ary infinite-horizon Markov decision processes". In: Advances in Neural Information Processing Systems 25 (2012).
13

---

[Sey+23] Erfan SeyedSalchi, Nima Akbarzadeh, Amit Sinha, and Aditya Mahajan. "Approxi- mate information state based convergence analysis of recurrent Q-learning". In: Euro- pean conference on reinforcement learning. 2023. URT.: nttps://arxiv. cwterxii.orrgoo .org arg/e //sbs/////// 2306. 2306.05991.
[Si++16] David Silver et al. "Mastering the game of Go with deep neural networks and tree search". In: Nature 529 (2016), pp. 489-
[SJJ94] Satinder P Singh, Tommi Jaakkola, and Michael I Jordan. "Learning without state- estimation in partially observable Markovian decision processes". In: Machine Learn- ing. Elsevier, 1994, pp. 284-292.
[SS73]
Richard D. Smallwood and Edward Sondik. "The Optimal Control of Partially OB- servable Markov Processes over a Finite Horizon". In: Operations Research 21.5 (Oct. 1973), pp. 1071-1088 DOr: 10. 1287 1287/opre 21.5.11..111 1071.
[SS04]
Trey Smith and Reid Simmons. "Heuristic search value iteration for POMDPs". In: Conference on Uncertainty Artificial Intelligence. Banff, Canada, 2004, pp. 520- 527.
[SVO5]
Matthijs TJ Spaan and Nikos Vlassis. "Perseus: Randomized point-based value itera- tion for POMDPs". In: Journal of Artificial Intelligence Research 24 (2005), pp. 195- 220.
[Ste+18]
Denis Steckelmacher, Diederik Roijers, Anna Harutyunyan, Peter Vrancx, Hélène Plis- nier, and Ann Nowé. "Reinforcement learning in POMDPs with memoryless options and option-observation initiation sets". In: Proceedings of the AAAI conference on tificial intelligence. Vol. 32. 1. 2018.
[Sub+-22]
Jayakumar Subramanian, Amit Sinha, Raihan Seraj, and Aditya Mahajan. "Approx- imate information state for approximate planning and reinforcement learning in par- tially observed systems". In: Journal of Machine Learning Research 23.12 (2022), pp. 1-83.
[Sut+99] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. "Policy gra- dient methods for reinforcement learning with function approximation". In: Advances in Neural Information Processing Systems. Vol. 12. 1999.
[SPS99]
Richard S Sutton, Doina Precup, and Satinder Singh. "Between MDPs and semi- MDPs: framework for temporal abstraction in reinforcement learning.. In: Artificial intelligence 112.1-2 (1999), pp. 181-211.
[SB08]
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2008
[VGS16]
Hado Van Hasselt, Arthur Guez, and David Silver. "Deep reinforcement learning with double q-learning". In: Proceedings of the AAAI conference on artificial intelligence. Vol. 30. 1. 2016.
[Vez+17]
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jader- berg, David Silver, and Koray Kavukcuoglu. "Feudal networks for hierarchical rein- forcement learning". In: International conference machine learning. PMLR. 2017, pp. 3540-3549.
[WS94]
Chelsea C White III and William T Scherer. "Finite-memory suboptimal design for partially observed Markov decision processes". In: Operations Research 42.3 (1994), pp. 439-455.
[WS97]
Marco Wiering and Jürgen Schmidhuber. "HQ-learning". In: Adaptive behavior 6.2 (1997), pp. 219-246.
[Wie+07]
Daan Wierstra, Alexander Foerster, Jan Peters, and Juergen Schmidhuber. "Solving deep memory POMDPs with recurrent policy gradients". In: International Conference on Artificial Neural Networks (ICANN). Springer. 2007, pp. 697-706.
[Wie+10]
Daan Wierstra, Alexander Förster, Jan Peters, and Jürgen Schmidhuber. "Recurrent policy gradients". . In: Logic Journal of the IGPL 18.5 (2010), pp. 620-634. Hans S Witsenhausen. "On policy independence of conditional expectations". In: In- formation and Control 28.1 (1975), pp. 65-75.
[Wit75]
[Zha09]
H. Zhang. "Partially Observable Markov Decision Processes: Geometric Technique and Analysis". In: Operations Research (2009).
14

---

Contents of Appendix
Illustrative examples
16
A.1 Ex. I: Learning curves for ASQI...
16
A.2 Ex. 2: non-stationary policies can outperform stationary policies
16
A.3 Ex. 3: stochastic policies can outperform deterministic policies
17
A.4 Ex. 4: conceptual difference between state-augmentation and periodic policies
18
B Periodic Markov chains
19
B.1 Time-homogeneous Markov chains and their properties
19
B.2 Time-varying with periodic transition matrix
20
B.3 Constructing equivalent time-homogeneous Markov chain
21
B.4 Limiting behavior of periodic Markov chain
22
C Periodic Markoy decision processes
24
Stochastic Approximation with Markov noise
24
Thm. 1: Convergence of periodic Q-learning
26
E.1 Step 1: State splitting of the error function
26
E.2 Step 2: Convergence of component X
26
E.3
Step 3: Convergence of component X
27
E.4 Step 4: Convergence of component X f.2
28
E.5
Putting everything together
30
Thm. 2: Sub-optimality gap
30
G Policy evaluation of an agent-state based policy
31
H Reproducibility information
31
15

---

A Illustrative examples
A.1 Ex. 1: Learning curves for ASQL
For each behavioral policy PR. k E K, we run PASQL for 25 random seeds. The median + in- terquantile range of the iterates {Qr(z, h2 as well the theoretical limits Qp (z, a) (computed as per Thm. for L = 1) are shown in Fig. 5. These curves show that the result of Thm. is valid for the stationary case (L as well.
(0.00)
P1
00000)
P2
230008
(
G (0.00
Pg
Katwet (0000)
Figure 5: ASQL iterates for different behavioral policies (in blue) and the limit predicted by Thm. (in red).
A.2 Ex. 2: non-stationary policies can outperform stationary policies
Example 2 Consider a POMDP with S = 7,,. A {0. and Y {0, 1}. The system starts an initial state 81 1 and has deterministic dynamics. To describe the dynamics and the reward function, define Do (r(n+11//2+1 E Zz DI N and D Do x (OJUDix [1] C A. Then, the dynamics, observations, and rewards are given by
8: + 1, (+), E D, otherwise,
[0, 1/2 - {1,
8t is odd, is even,
+1, (s, E E r(s,a)={_1 [-1 otherwise.
8t+11
11
r(s,a) -
Thus, the state is incremented if the agent takes action 0 when the state is in Do and takes action when the state in reward of -1 and resets the state to 1. The agent does not observe the state, but only observes whether the state is odd or even. A graphical representation of the model is shown in Fig.
D,. Taking these actions yield a reward +1. Not taking such an action results
7
12
13
14
15
Figure 1: Graphical representation of Ex. 2. The cells indicate the state of the environment. Cells with the same background color have the same observation. The cells with thick red boundary correspond to elements IN), where the action gives reward of +1 and moves the state cells with a black boundary
of the Do = (nin 1)/2 the right, while action gives reward correspond to elements of the set D, = IN Do. where the action gives the reward +-1 and moves the state to the right while the action 0 gives reward of -1 and resets the state to 1. Discount factor = 0.9.
and resets the state
For policy class TED (the class of all belief-based deterministic policies), since the system starts in known initial state and the dynamics deterministic, the agent compute the current state
16

---

-l..... Thus, the (thus, the belief is delta function on the current state). Thus, the agent can always choose the correct action depending on whether the state is in Do and D,. Hence J 1/(1 - 7), which is the highest possible reward.
For policy class ST (the class of all agent-state based deterministic policies), there are four possible deterministic policies. For odd observations, the agent may take action 0 and 1. Similarly, for even observations, the agent may take action 0 or Note that the system starts in state which is in Do- Therefore, if the agent chooses action when the observation is odd, it receives a reward of -1 and stays at state 1. Therefore, the discounted total reward -1/(1 - -7), which is the least possible value. Therefore, any policy that chooses 1 on odd observations cannot be optimal. Therefore, the optimal (deterministic) action on odd observations is to pick action 0. Thus, there are two policies that we need to evaluate.
the agent chooses action at both odd and even observations, the state cycles between 1 + 2 + 3 - + 2 + .... with the reward sequence cumulative total reward of this policy is 71+7-- >-)(111
the agent chooses action 0 at odd observations and action at even observations, the state cycles between 1 + 2 - 1 + 2.... with the reward sequence (+1, +,, -1... Thus, the cumulative total reward of this policy is 1/(1 + 7).
It is easy to verify that for (0, 1), 1/(1 + 7) < (1 + 7 721(1 -79). Thus,
1 7
J/ 1 73
We also consider policy class lsss: the class all stationary stochastic agent-state based poli- cies. For policy class IIss, the policy is characterized by two numbers (Po. p1) [0. 1]², where Py denotes the probability of choosing action 1 when the observation is y. y E 10. We compute the approximately optimal policy by doing brute force search over (po, P1) by discretizing them two decimal places and for each choice, running a Monte Carlo simulation of length 1, 1,000 and averag- ing it over 100 random seeds. We find that there is negligible difference between the performance of stochastic and deterministic policies.
Finally, we consider policy class II, which is the class of periodic deterministic agent-state based policies. A policy æ E II, is characterized by two vectors po, Pi 10,1 where Py. denotes the action chosen when i mod L = l and the observation is y. We do an exhaustive search over all deterministic policies of length L, L E (1...., 10) to compute the numbers shown in the main text.
A.3
Ex. 3: stochastic policies can outperform deterministic policies
When the agent state is not an information state, the optimal stochastic stationary policy will perform better than (or equal to) the optimal deterministic stationary policy as observed in [SIJ94]. Here is an example to illustrate this for a simple toy POMDP.
1
0.5
0.5
0.5
0.5
Q
0
0
2
0.5
0.5
(a) Dynamics under action 0
(b) Dynamics under action
Figure 6: The dynamics for Ex. 3.
Example 3 Consider a POMDP with S = (0, 1, 1, A = (0, and Y = {0]. The system starts
initial state 81 0 and the dynamies under the two actions shown in Fig. 6. The agent does not observe the state, i.c., Y = 0. The rewards under action 0 are r(. 0) = =_-1, rewards under action 1 are r(s, 1) = -0.5, for all s S.
0, 2] and the
17

---

We consider agent state Z. Y. Let Ilss denote the of all stationary stochastic policies and Tlsn denote the class of of all stationary deterministic policic policy æ sss is pa- rameterized by single parameter E [0, 1]. which indicates the probability of choosing ac- tion 1. We denote such policy by TT. Note that p E {0, 1), "p E Isn-- Let (a))Ta denote the probability transition matrix and reward func-
-10
0.00
0.25
0.50 0.75
1.00
Figure 7: Performance of stationary stochastic policies Tp for p E [0, 1] for Ex. 3.
tion when a E A is chosen and let (Pp: Tp) (1 (1-11)ppp) ()o. + p(P1.r1). Then, the performance
of policy "p is given by , = [(1 - P The performance for all E [0, 1] for 7 = 0.9
shown in Fig. 7, which shows that the best performance is achieved by the stochastic policy γp with p x 0.39.
Thus, stochastic policies can outperform deterministic policies.
A.4
Ex. 4: conceptual difference between state-augmmentation and periodic policies
G₁
8
2
2x
T
G2
2n cells
Figure T-shaped grid world for Ex. In state s, the agent learns about the goal state. states (1,2,..., 2n), , the agent simply knows that is in the gray corridor, but does not know which cell it in. In state T, it knows that it has reached the end of corridor and must decide whether to go up or down. The agent gets reward of +-1 for reaching the correct goal state and reward of - for reaching the wrong goal state.
Example 4 Consider a T-shaped grid world showed in Fig. 4 with state space x G, where (s, 1, ... 2n, т is the position of the agent and G {G1, G2 is the location of the goal. The observation space is Y = 2,,,33 The observation is a deterministic function of the state and is given follows:
At state (s, G.). E {1,2), the observation is and reveals the location of the goal state the agent.
At states {l,..., 2n} x G, the observation is 0, so the agent cannot distinguish between these states.
At states {T} G, the observation is 3. so the agent knows when it reaches the state.
The action space depends on the current state: actions {LEFT, RIGHT, STAY) } are available when the agent is at {s, I,.., 2n} and actions {UP, DOWN) are available at position T.
The agent receives reward of +1 if it reaching the goal state and -1 if reaches the wrong goal state state (i.e., reaches G2 when the goal state is Gj). The discount factor 1.
We consider classes of policies:
(i) TTD (m): Stationary policies with agent state equal to sliding window of the last m observations and actions.
iii I1: Periodic policies with agent state equal to the last observation and periodic L.
is easy to see that as long as the window length m S 2n, any policy in (m) yields an average return of 0: for window lengths m > 2n, the agent can remember the first observation, and therefore it is possible construct a policy that yields a return +1.
We now consider a deterministic periodic policy with period I, = given as follows: क = (Ir", x!_,²) m²) where स" Y -> A. We denote each oe column vector, where the y-th compo- nent indicates the action n (w), where means that the choice of the action for that observation is
For the ease of notation, start the system time 0.
18

---

irrelevant for performance. The policy is given by
RIGHT
RIGHT
STAY
RIGHT n².
x²
STAY STAY
RIGHT UP
DOWN
It is easy to verify if the system starts in state (0, G1), then by following policy (T², m²), the agent reaches state G1 at time 3n + Moreover, when the system starts in state (0, G2), then by following the policy (rr x!, >²). the agent reaches G2 time 3n + 4. Thus, in both cases, the policy (T", x², T²) yields the maximum reward of +1.
B Periodic Markov chains
In most of the standard reference material Markov chains, assumed that the Markov chain is aperiodic and irreducible. In our analysis, we need to work with periodic Markov chains. In this ap- pendix, review some of the basic properties of Markov chains and then derive some fundamental results for periodic Markov chains.
Let be a finite set. A stochastic process {Si St S, is called Markov chain if it satisfies the Markov property: for any E Zzo and $1:t1 E Si+11 we have
P(S $1+1 S1 814) PS 8141 S =s))-
is often convenient to assume that S = [1....,1] n). We can define an n x n transition probability matrix Pt given by [Pi]i PS Markov chain is described by the transition matrices (Po. .).....
S, i). Then, all the probabilistic properties of the
In particular, suppose the Markov chain starts at the initial PMF (probability mass functioo) &o and let & denote the PMF at time t. We will view & as a n-dimensional row vector. Then, Eq. (4) implies &++1 E,P, and, therefore.
Eo P.-
B.1 Time-homogeneous Markov chains and their properties
A Markov chain is said to be time-homogeneous if the transition matrix P; is the same for all time t. In this section, we state some standard results for homogeeegss Markov chains [Nor98].
B.1.1 Classification of states
The states of hime-homogeneous Markov chain can be classified as follows.
We say that a state j is accessible from (abbreviated as j) if there is exists an m E Zzo (which may depend on i and j) such that [Pm) > 0. The fact that [Pm > 0 implies that there exists an ordered sequence of states (ig....,fe fm.) such that in i and im
such that
Pichei > O; thus, there is path of positive probability from state i state j. Accessibility is transitive relationship, i.c., if ~ and j k implies that i ~~ k.
2. Two distinct states and j are said to communicate (abbreviated to m- j) if is accessible from j (i.e., j ~ i) and j accessible from i ~9 j). Alternatively, we say that i and communicate there exist m, mr E Zzo such that [Pm"],; > 0 and [PMM] 1, >
Communication is an equivalence relationship. i.c., it is reflexive (i exs i), symmetric (i ews j and only if m- i), and transitive (i mm j and .. implies i me k).
3. The states in finite-state Markov chain can be partitioned into two sets: recurrent states and transient states. A state is recurrent if it accessible from all states that are from (i.e., recurrent if é ~ j implies that j ~e i). States that are not recurrent are transient.
It can be shown that state is recurrent if and only if
P a
30.
19

---

4. States i and j are said to belong to the same communicating class if i and j communicate. Communicating classes form partition the state space. Within a communicating class, all states are of the same type, i.e., either all states are recurrent (in which case the class is called recurrent class) or states are transient (in which case the class is called a transient class).
Markov chain with a single communicating class (thus, all states communicate with each other and are, therefore, recurrent) is called irreducible.
5. The period of a state i, denoted by d(t), is defined as
d(i) = ged(t E Zz1 : [P*], > 0}.
If the period is 1, the state is aperiodic, and if the period is 2 more, the state is periodic. It can be shown that all states the same class have the same period.
A Markov chain is aperiodic, if all states are aperiodic. A simple sufficient (but not necessary) condition for an irreducible Markov chain be aperiodic is that there exists a state such that Pa > O. In general, for finite and aperiodic Markov chain, there exists positive integer 7 such that
P > 7.TTiES
B.1.2 Limit behavior Markov chains
We now state some special distributions for a time-homogeneous Markov chain.
1. A PMF ( on S is called stationary distribution if Ç ÇP. Thus, if a time-hoomgennous) Markov chain starts in stationary distribution, it stays in a stationary distribution.
finite irreducible Markov chain has a unique stationary distribution. Moreover, when the Markov chain is also aperiodic, the stationary distribution is given by {(j) 1/my, where m, is the expected return time to state j.
PMF on S is called a limiting distribution if
lim [P ((), Vi,j E.
finite irreducible Markov chain has a limiting distribution and only it is aperiodic. There- fore, for aperiodic Markov chain, the limiting distribution is the same as the stationary distri- bution.
Theorem (Strong law of large numbers for Markov chains, Theorem 5.6.1 of [Dur19]) Suppose {Sthe21 is an irreducible Markov chain that starts in state i E S. Then,
lim T
Σ 1=0
11St 5) mj
Therefore, for any function h: S + R,
T-1 h(S.)
M(j) m,
lim T
(5)
T
1=
jes
If. addition, the Markov chain (Se)121 is aperiodic, and has limiting distribution Ç. then have that
lim T-
Σ (SS))
ΣCOMOO.
(6)
T
1=0
JES
B.2 Time-varying with periodic transition matrix
In this section, we consider time-varying Markov chains where the transition matrices (Po, ......) are periodic with period L. Let [[]] = (t mod L) and L (O..... - 1}. Then, the transition completely deseribed by the transition
matrix P. is the same as Piy-- Thus, the system dynamics matrices (Pr (ee) With a slight abuse of notation, we will call such a Markov chain I-periodic Markov chain. We will show later that the notion of -imepperidiccttyy that we are considering equivalent to the notion of state periipeeriy for time homoghooogsssuus Markov chains defined carlier.
20

---

B.3 Constructing an equivalent time-homogeneoos Markov chain
Since the Markov chain not time-homogeneous, the classification and results of the previous section are not directly applicable. There are two ways to construct time-homogeneous Markov chain: using state augmentation or viewing the process after every steps.
B.3.1 Method State augmentation
The original time-varying Markov chain {St)220 is equivalent to the time-homogeneous Markov chain f(S,, h20 defined on with transition matrix P given by
P((s' ( (s, ()) Pe(s' ss) = [e + 1]}.
Example 5 Consider 2 2-periodic Markov chain with state space S [1,2) and transition matrices
3 4
3
Po
4
and Pi
4
The time-periodic Markov chain of Ex. 5 may be viewed time-homogeneous Markov chain with state space {1, x {0, } and transition matrix
(1.0)
(2.0)
(1,1)
(2.1)
(1.0)
0
i
P
(2.0)
0
0
2
1
To
1
Po
0
(1.1)
3
1
0
0
[
0
P
1
7
(2.1)
where 0 denotes the all matrix and I denotes the identity matrix (both of size 2 x 2). Note that the time-homeen homogeoogge Markov chain is periodic.
Define the following:
block diagonal matrices Ao,...,AL-- E Ru.xal as follows:
Ao = blkdiag( Po, Pi,..., PT.-)), A = blkdiag(PP Sakddaa((P.-1,. Po...., Pt.-2), etc.
permutation matrix IT E (0, 1]nlxnt as follows
0 I
07
II
I
0
0
where each block is
The permutation matrix satisfies the following properties (which can be verified by direct algebra):
(P1) I and therefore II ITT.
(P2) IT I.
(P3) A,ll 1AA LEL.
In general, the transition matrix of the Markov chain {(St, [t]) is
Po
0
Agll.
Pt-2
PL-1
nLxnL
21

---

B.3.2
Method 2: Viewing the process every L steps
The original Markov chain viewed every L-steps, iee, the process (SkL+e) & E L, is time- homogeneous Markov chain with transition probability matrix Pe given by
Pe Pa=Paa Pe+il PletL-11
that is,
Po = PoPl ... PE-2PE-1 P ... PL-IPO. etc.
B.3.3 Relationship between the two constructions
The two constructions are related follows. Proposition 1 We have that p7
(Po....
PROOF From (P3), we get that P = IIA Therefore,
p2 = AolTAolT = A0
Similarly
p3 Aol1P2 AoLIAaA,1I = II = A21
Continuing this way, we get
p = AgA1 ................................ AL-IlI AgA1 AL-11
where the last equality follows from (P2). The result then follows from the definitions of As and P. f L.
D
B.4 Limiting behavior of periodic Markov chain
In the subsequent discussion, we consider the following assumptions. Assumption Every (Pe), E L, irreducible and aperiodic
Suppose Assm. holds. Define ç to be the unique stationary distribution for Markov chain Pe. Ê E L,i,, Ç is the unique PMF that satisfies Ç Pp'
Proposition 2 The PMFs JEEL satisfy
P c L
PROOF We prove the result for l = The analysis the same for general &. By assumption, have that
0 c = P PL-1-
Let 5' = P Then, we have
c = PoP ... PL = P - P
Thus 2t is a stationary distribution. Since P1 is irreducible, the stationary distribution is unique, hence (1 must equal 2²
D
We can verify this result for Ex. 5. For this model, we have
Po = Pol
and
P = PiPo
16
7
16
16
Thus,
5"
and <²
T
11
18
And we can verify that Po 5² and P2 Co Proposition 3 Under Axsm. 3, the limiting distribution of the Markov chain (Sthe2 is cyclic. In particular, for any initial distribution Eo.
lim ExL.4 5t 100
22

---

Furthermore,
K K-1
lim sup K-000
if (5%,, Vi
k=0
Consequently, for any function h: S R,
K-1
sES lim h(Sa.+t)= ME E K-oc K
(8)
k=0
PROOF The results follow from standard results for the time-homogeneous Markov chain (SkL+e)<20-
PROoF (ALTERNATIVE) We present an alternative proof that uses the state augmented Markov chain P. We first prove that under Assm. 3, the chain P is irreducible periodic with period L.
The proof irreducibility relies on two observations.
1. Fix an i E L and consider j.j S. Since Pe is irreducible, we have that there exists positive integer m (depending on i, j. and E) such that [Pt*)s > Note that Prop. implies that [pmL (6.00.0.) = [Pr]e > 0. Therefore, in the Markov chain P, states (i, E) ~ (j, Since and were arbitrary, all states
{(} belong the same communicating class.
Now consider two l' L. Suppose
start some state (i, E Ex {f), then in [E" - steps, we will reach some state (j, (') E S x {('}. Thus, (j, (') is accessible from (i, But, we have already argued that all states in S x {E} belong the same communicating class, therefore all states in S x {E'} are accessible from all states in S {{}. By interchanging the roles of and f", we have that all states in S {L} are accessible from all starts in S {E'). Therefore, the states S x {E} and S } belong to the same communicating class. Since l and l' were arbitrary, we have that all states of P belong to the same communicating class. Hence, P irreducible.
We now show that P is periodic. First observe that the Markov chain starting in the set S x {L} does return to the same set for the first L- steps. Thus, (1.0,.0))))))) = 0 for E (1,2..... 1}. Therefore, the only possible values for which [P* (6.0).00.) are those that are multiples of L. Hence, for any (i, E) x
d(i, e) = ged(t E Z21 : [P')),,) 0} Ledffk E Zz1 [P/] 0}
Moreover, since Pe aperiodic, gedfk e Eد1 : [P]]i > 0} = 1. Substituting in (9), we get that d(i, E) for all (i, l). Thus, all states have period of L.
Now, from Prop. 1, we know that pr. blkdiag(Pu..... PL-1). Therefore
lim PbL (000.00 = (s',, (1, xx 10000
Consequently, if we start with an initial distribution & such that Eo(S x {0}) 1, then,
lim EuL vec(So. .). 100
where the vectors are of size n. Consequently, Prop. implies that
lim EaL+E ... Se. O, O)...,,), vl E
1000
where ç is the f-th place. This completes the proof of (7).
Now consider the function h: x L + R. defined as his, (') h(s)1[{( = C}. Then, by taking
T = KL, we have
K Σ 1=
L T
h(S. [t]] = L Σ h(s)
lim 100
h(ShL+e)
lim
K
T-000 T
#ES
where the last equation uses (5) from Thm. 3. Now, (8) follows from observing that mean return time to state (s, in Markov chain P is L times the mean-return time to state in Markov chain Pt. which equals 1/ since P; is irreducible and aperiodic.
23

---

C Periodic Markov decision processes
Periodic MDPs are a special class time non-stationary MDPs where the dynamics and rewards are periodic. In particular, let M be timevarrying MDP with state space S, action space A, and dynamics and reward at time t given by P.:
> (()) and rt: S - R.
As before, we use [4] to denote mod L and L to denote {0, L 1}. The MDP M is periodic with period L if there exist (P',r"), l E L such that for all t:
Pt St, A.) plll (S.+1 A.) and (r A.) - (S,, A.).
Periodic MDPs were first considered in [Ri65]. Periodic MDPs may be viewed as stationary MDPs by considering the augmented state (S,, [t]]. By this equivalence, it can be shown that there is no loss of optimality in restricting attention to periodic policies. In particular, let (Vo, VL-1) denote the fixed point of the following system of equations
(s) max r² (s, a) + Σ ('(((1ss.))vl++ S'ES
V(l.s,,)ExxSx(
(10)
aeA
Define (s) to be the arg-max or the right hand side of (10). Then the time-varying policy
(m1, T2, .... given by n, ! optimal.
See [Sch16] for a discussion of how to modify standard MDP algorithms to solve periodic dynamic program (10).
D Stochastic Approximation with Markov noise
We now state a generalization of Thm. 3 to stochastic approximation style iterations.
Theorem Let {Se)t21, S, be an irreducible and aperiodic finite Markov chain with unique limit- ing distribution Ç. Let F, denote the natural filtration w.r.t {Seht21 and {0r)121 be a non-negative real-valued process adapted to {Fi} that satisfies
-a== and Lat <0. 121
(11)
21
Let (M++1121 be square-integrable margingale difference sequence w.r.f. (Fi)t21 such that E[M2+1 Fi] < K(1 22) for some constant K. Consider the iterative process (X,h2n where X1 is arbitrary and for 2 1, we have
X (1 X,) + ar (M(S)) + M--]
(12)
Then, the sequence {X1h121 converges almost surely limit. In particular,
lim X Σ h(s)((s),
a.s.
(13)
#ES
Eq. (12) is similar to standard stochastic approximation iteration [RM51: KY97; Bor08), which the "noise sequence" h(S.) is assumed be a martingale difference sequence. The setting considered above is sometimes referred to stochastic approximation with Markov noise. In fact, more general version of this result where the noise sequence is allowed to depend on the state X, are typically established in the literature [BMP12; Bor08; KY97; PB24]. For the sake of completeness, we will show that Thm. 4 is special case of these more-general results.
Before presenting the proof, we point out that Thm. 4 is generalization of Thm. 3. Eq. (6). In particular, suppose the learning rates are a; 1/(1 + t). Then, simple algebra shows that
T
X² = T Σ h(S))
Then, (6) of Thm. implies that the limit is given by the right had side of (13). Therefore, Thm. a generalization of Thm. 3 to general learning rates which satisfy (11).
24

---

PROOF To establish the result, we will show that the iteration {X1)e21 satisfies the assumptions for the convergence of stochastic approximation with (state dependent) Markov noise and stochastic recursive inclusions given in [PB24, Theorem 2.7]. The proof is due to [BP24]. In particular, we can rewrite (12) as
X1+1= X, + (x, where g(z, s) x + h(s). Moreover, for ease of notation, define h = ExEs h(s)((s). Then, we have
ga, s) is Lipschtiz continuous in the first argument, so A2.14 of [PB24] holds.
From (6), the ergodic occupation measure of (l(5)))221 (h), which is compact and convex.
So, A2.15 of [PB24) is satisfied.
The conditions on the martingale noise sequence {Me)e1 imply that A2.16 of [PB24] holds.
Eq. (11) is equivalent to A2.17 of [PB24].
To check A2.18 of (PB24), for any measure S, define
h(z,v) / g(z, s)v(ds) - h.
Also define
he( h(cr,ev)
Let h = lim ho(x, = Thus, the differential inclusion in A2.18(i)) is actually an ODE
which has origin as the unique global asymptotically stable equilibrium point. Thus, A2.18 of [PB24] is satisfied.
Therefore, all assumptions of Theorem 2.7 of [PB24] are satisfied. Therefore, by that result, the iterates (X,)22 converge to solution of the ODE (note that the differential inclusion in Theorem 2.7 of [PB24] is an ODE our setting)
f = -
(14)
Note that = is the unique asymptotically stable attractor of the ODE (14). Therefore, Theo- rem 2.7 of [PB24] implies (13).
Thm. 4 also implies the following generalization of Prop. 3.
Proposition 4 Suppose {Sth11 is time-periodic Markov chain with period L that satisfies Assm. 3 with the unique limiting distribution { heLL Let {Fi)121 denote the natural filtration w.r.t. {Stfe2 and {at E L, be non-negative real-valued processes adapted to {FeJe21 such that of = 0 when + [4] and
- and {(a) <0.
E21
12
Let (Me+1de2) be square-integrabl margingale difference sequence W.E.t. {Fitez such that E[M2+1 [F] K(1 + { some constant K. Fix any E E Consider the iterative process {X where X1 is arbitrary and fork k 2 1, we have
x = (1 -1-o x + ((())))) + Me+1].
(15)
Then, the sequence (X/121 converges almost surely to the following limit
lim x Σ (s))((
#ES
PROOF Note that the learning rates used here can be viewed as the learning rates of L separated stochastic iterations a common timescale t. Each separate stochastic iteration é E L is actually only updated once every L steps on the timescale t. Because of the condition of = 0 when É + [[]] where the learning rate is 0. Therefore, each X updated only once every L. steps timescale I.
each update followed by
The result then follows immediately from Thm. by considering the process (St)e2 every steps for each E L.
25

---

E Thm. 1: Convergence of periodic Q-learning
The high-level idea of the proof similar to [KY22] for ASQL when the agent state is a finite window of past observations and action. The key observation of [KY22] is the following: Consider an iterative process X = (z)x; + a,U, with the learning rates a; = 1/(1 + t). Then, Xx+1 = (X, + - 0,)(11+)) t). Then, if the process {Uth21 has an ergodic limit (c.g., when (21 is function of Markov chain, Thm. 3), the process (Xe)121 converges to the ergodic limit of {2) We follow similar idea but with the following changes:
Instead of assuming "averaging" learning rates (i.e., reciprocal of the number of visits), we allow for general learning rates of Assm. 1.
We account for the fact that that the "noise" is periodic.
The rest of the analysis then follows along the standard argument of convergence of Q- learning [JS194; KY22; DY24].
Define the error function Af41 == Qi+1 og for all e To prove Thm. it suffices to prove that | + 0 for all e L, where ||-I| is the supremum-nome The proof proceeds in three steps.
F. Step 1: State splitting of the error function
Define (x) max.ca (2 a) and (=) maxaca (z, for all / L, Z. We can combine (PASQL.. (1), and (2) as follows
A 1/41 (2, ((1-a((z.)))4((t ( (2, (22 (16)
where
U2-0 = [r(Se, At) -r 11 ((1=,,A)==);
U [-V[et (Ze+1) - Σ ()) (z*) (12==AA1=a))
z'EZ
(2,0) [V!et1] (2++1) - (V/(+t
Note that we have added extra indicator functions in the Ufi (z, a) terms, E {0, 1}. This does not change the value of (z, a)U,f'(z, a) because the learning rates have the property that af a) = if (L, a) * ([t], 24, at) (see Assm. 1).
farc l L, Eq. (16) may be viewed as linear system with state A4+1 and three inputs U..00. .U..1. and U. We exploit the linearity the system and split the state into three components: A =
x xx11 -x where the three components evolve follows:
X/4 (z, a)
(z. x)
(z, (z,a), ie {0, 1,2)
(17)
Linearity implies that (16) is equivalent to (17). We will now separately show that ||xx -> 0. ||x-11 '1 and [ 0.
E.2 Step 2: Convergence of component X-.0
Fix (E, 2o, ao) x x A and define
hS,, Zr, Ari A, ac) = [r(Stt Ar) -r az)] A1=00))
Then the process {X," 6.0 (2o, ao) ho21 is given by the stochastic iteration
x (zo, ac) = (1 (z0, a. x (zo, a.) + af a. h, Z,, A,, ao):
which is of the form (15). The process (S, Z,, A1) is periodic Markov chain and the learning rates (af(= ax)) satisfy the conditions of Prop. 4 due to Assm. 1. Therefore, Prop. 4 implies
26

---

that {x, 2.0 (Zo, tol converges a.s. to the following limit
lim X, ao)
Σ a,2xESSZxx
(,,
Σ
() ( (r(s,)) (2o.
5,20ESxZXA
- 2, (o)
ES
Σ
(s (b)
Σ
(0 ae) ((l
(s 2o 20)
ES
SES
Hence, for all (l, Ro, as), the process {x (zo, do)1 converges to zero almost surely.
E.3 Step Convergence of component X
Let W;, denote the tuple (Se, Ze, Ar, S1+1. Z,+1, Ast1). Note that (Wehe21 is also a periodic Markov chain and converges to a cyclic limiting distribution çy where
(5,
Σ Y'EY
We use E (s, a, S, A, denote the marginalization over the "future states" and similar notation for other marginalizations. Note that Ey a,
(5,
Fix (e, t0, zo, a.) E x Z x A and define
hr(We; 2o, a.) [ (Z+t1) 7 Σ
(1 a.) V (z) 1 12,
sEZ
Then the process (x, (x (z, a)21 is given by the stochastic iteration
x11 (20, ao) = (1 - az (())) Xx (zo, a.) + af ao).u E, Ro, ao)
which is of the form (15). As argued earlier, the process (We is periodic Markov chain. Due to Assm. 1, the learning rate af (2,, a.) is measurable with respect to the sigma-algebra generated by (Zi,, A1:) and is therefore also measurable with respect the sigma-algebra generated by Wi:-- Combining this with Prop. 4 implies that the learning rates (af(zo, a.) satisfy the conditions of Prop. 4. Therefore, Prop. 4 implies that {x, (zo: h2) converges a.s. to the following limit
lim X (Zo, ao) 10000
Σ SEZ.ES d'EEZAA
Σ
2, (2))-
Σ ZEZ
pt M
(El a v/e+11 (==10.==a))
B,Z,EESXZAA d'ESZZAA
Σ (S 2o, a. S, 2.2 EEEZ
(5, 2o, a., S,2,A)
Σ
(E a. V/!ct1
ZEZ
where the last step follows from the fact that (, Zo, do, S, (S, 2o, ao, S',,A) (Eo, a.) Pf ao).
c((zo; (o) and
27

---

E.4 Step 4: Convergence of component X
The remaining analysis is similar to corresponding step in the standard convergence proof of Q- learning and its variations [JSJ94; KY22; DY24]. In this section, we use ||-|| to denote the supremum norm, i.c., sl
In the previous step, we have shown that |X + a.s., for {0, 1). Thus, we have that ||xx + x + a.s. Arbitrarily fix an 6 > 0. Therefore, there exists set Q of measure one and constant ((w, e) such that for w E Q all t >> T(w, c), and 2,) L Z x A, we have (2, a) + X (z, a) <e.
(18)
Now pick constant C' such that
K k=
1+ C <1
(19)
Suppose for some I > T(w, t), maxtel |x,21 > Ce. Then, for (z, E Z A,
U.. (2, = vV. (Z++1) - - 7/[++11 (1+11)
/
7 max Ql 1e+1] (244, d'EA
[[+1]] Q[(+11
(242,ad))
max
aEA
S max 1 11+1| (1 a) -1 AEA
|[+1| (2(+1,
(0)
S -
1114111 = ? |e+1|||
-
x/|x(et11.00 x
|e+1].111
>|| x||x!((t|) [
(6)
- 76 + 7 x|| 1
(20a)
r 1+
d)
max
X
max
2
<
(d)
max
(20b)
REL
ZEL
EEL
where (a) follows from the fact that an upper bound is obtained by maximizing over all realizations
of Zut1. (b) follows from (18), (c) follows from the fact that maxeel x|x Ce, (d) follows
from (19). Thus, for any > T(w,e) e) and maxxeellxx 2:2 > Ce, we have
2 a) = (1 a x)) (2, a) + ()) < max||xx
rEL
max KEL
x < |
EEL
Hence, when maxreL X > Ce, decreases monotonically with time. Hence, there are two possibilities: either (i) max always remains above Ce; or (ii) it goes below Ce at some stage. We consider these two possibilities separately.
E.4.1 Possibility (i): max+el X always remains above Ce
We will show that maxrel || [ cannot remain above Ce forever. We first start with basic result for random iterations. This a self-contained result, so we reuse some of the variables used in the rest of the paper.
Lemma Let (Xi)e2, (Y)e,, and (at)121 be non-negative sequences adapted to a filtration (Fihiz that satisfy the following:
X S (1 - at)
(2la)
Y+1 < (1 - Yr a,c,
(21b)
where e is a constant. Suppose
2
Σ a4 0
(22)
1=1
Then, the sequence (X:)121 converges to zero almost surely and the sequence (Yire) converges to almost surely.
28

---

PROOF The iteration (21a) implies that
X--1 (1-wi)-.. ... (1 an) X1
Condition (22) implies that the term in the square brackets converges to zero. Therefore, X, - 0. Observe that the iteration (21b) can be rewritten as
Y++ - c -c -c)
which is of the form (21a). Therefore, Y, c O.
We will now prove that max || cannot remain above Ce forever. The proof is by con- tradiction. Suppose max remains above Ce forever. As argued earlier, this implies that maxxell|xx 2 T(w, e), is strictly decreasing sequence, so it must be bounded from above. Let (())) be such that max S ((0) for all > T(w, Eq. (20b) implies that || <B(()), Then, we have that
max X (2,1(2, a) S (1 a (z, a))
max
X 2 + of (z, a) max |
REL
EEL
REL
(1 - (5( a))
max
X 2 + of (z, a) max X x
EEL
EEL
which implies that max || [x < I (,( 1. where {M, (M,.(0) (12)( is sequence given by
M (z, a) s (1 - (2, M (0)
(2, (z af(2,a) v(z,a)
Lem. 2 implies that M, M, (0) (2, a) + RB and hence || RB(O), Now pick arbitrary E (0. (1 xt)Ce). Thus, there exists time T() T()) (w, such that for all > TO), ||M, < B()) = kB()) + Since maxeel||xx is bounded by [|M, this implies that for all >> T(), maxxe ||x, s g()) and, by (20b). || & kB()), By repeating the above argument, there exists a time (22) such that for all 2 T2).
|X 22 < B(2 = kB()) +E= (() + KË KE
max REL
and so on. By (19), K
and chosen to be less than Ce. So eventually, B(m) = k. B(O) + Rth -m- ... + must get below Ce for some m, contradicting the assumption that xxx remains above Cc forever.
E.4.2 Possibility (ii): maxtel [x goes below Ce at some stage
Suppose that there is some T(w, e) such that maxeel xxx Ce. Then (20a) implies that
|| S >||x! 1++10. + x! x +| + !
11-11 S 7e + 7Ce < Ce
where the last inequality (19). Therefore,
max
x xax (1 af(2, max
+ af a) max Co x X
EEL
SEL
EEL
where the last inequality uses the fact that both || and max x s+1ll ll are both below Cc. Thus, we have that
max X. (z, a) Ce.
ZEL
Hence, once max (
2 goes below Ce, it stays there.
E.4.3 Implication
We have show that for sufficiently large t > T(w, c), maxtEt x < Ce. Since c is arbitrary, this means that for all realizations w E Ω2,, max + 0. Thus,
lim ma
f.2 = =0 a.s.
(23)
EEL
29

---

E,5 Putting everything together
2 + xx. Steps 2 and 3 together show that x + x + O, a.s. and Step (23) shows that maxret 11 - O.
Recall that we defined A = Qi Q2 and in Step 1, we split A = x + xx2tt
a.s. Thus, by the triangle inequality.
lim |ل & lim xx + x +|+ lim 1-0
| = 0,
1-000
which establishes that Of - Qu a.s.
Thm. 2: Sub-optimality gap
The high-level idea of proving Thm. 2 is follows. Thm. 1 shows that PASQL converges cyclic limit, which is the solution to a periodic MDP. Thus, the question of characterizing the sub- optimality gap is equivalent the following. Given PODMP P. let M be periodic agent-state based model that approximates the reward and the dynamics of P (in the sense of an approximate information state, defined in [Sub+22]). Let Æ* be the optimal policy of model M. What the sub-optimality gap when f* is used in the original POMDP P?
To answer such questions, general framework of approximate information states was developed in [Sub+22] for both finite and infinite horizon models. However, we cannot directly used the results of [Sub+22] because the infinite horizon results there were restricted to stationary policies, while are interested in the sub-optimality gap of periodic policies.
Nonetheless, Thm. 2 can be proved by building the existing results of [Sub+22].. In particu- lar, we start by looking at finite horizon model rather than infinite horizon model. Then, as per [Sub+22, Definition 7], the agent state process may be viewed as an approximate information state with approximation errors (.t,,1))211 where
2/,)
sup [R h1, at)
hs
#ES
& sup d3 (P(Z-1= = 1 (,));,, p!d (7e+1 -lox(he),
ha,as
Let (h+) (" R, hr] denote the value function of policy म for the finite horizon model starting at history he time t. Let (h,) sup, (hx) denote the optimal value function, where the optimization is over all history dependent policies. Moreover, let V Vz.(Ze) denote the optimal value function for the periodic MDP model constructed in Thm. Let T.. denote the history-based based policy defined in Sec. 2.4.
Then, from [Sub+22, Theorem 9] we have
T Σ 7" " 7=1
sup (Vtr - (hv) 2 he
(24)
where we set (=) = 0 for convenience.
The following hold when we let T - 00.
Since R₂ uniformly bounded, (ht) Vi+(he) as T + cc.
By the same argument, Vi
7. (h+) T + co.
By standard results for periodic MDPs (see App. C), Vi - v as + co.
By definition, e S et and 6, < s!dl Therefore, by taking T in (24), we get
sup v. u. (h+)] < Σ - 76!=1 p3 (VI++1]3].
T=1
The result then follows from observing that for 7 E T(t, E), ef and of are non-decreasing sequences.
30

---

G Policy evaluation of an agent-state based policy
The performance of any agent-state based policy can be evaluated via a slight generalization of "cross-prees "ccoss-productt MDP" method originally presented in [Pla77]. This method has been rediscovered in slightly different forms multiple times [Lit96; Cas98; Hau97; Han98].
The key intuition is Lem. 1. Thus, for any agent-state based policy, {(St. Ze) is a Markov chain. The only difference in our setting is that the Markov chain is time-periodic. Thus, for any periodic agent-state based policy (T "r",...,""" ---),, we can identify the periodic rewards (_-...,--1) and
periodic dynamics (Po. ..... 1L- (which depend but are not carrying that dependence in
our notation) as follows:
(8, Σ (al
acA
('
Σ
(v.a)EYxA
We can then evaluate the performance of this time-periodic Markov chain via performance evalua- tion formulas for periodic MDPs (App. C). In particular, define
70 p po pL-2p1-11
p pD p PL-1
to be the I-step cumulative rewards and dynamics for the time-periodic Markov chain. Then define
V (1-11~"P))
Thus, (ss, 2) gives the performance of periodic policy when starting at initial state (s, 2). If the initial state stochastic, we can average over the initial distribution.
H Reproducibility information
The hyperparameters for the numerical experiments presented in Sec. 3 are shown in Table 3. The experiments were run on a computer cluster by running jobs that requested 2-CPU nodes with < 8GB memory. Each seed typically took less than 10 minutes execute.
Table 3: Hyperparameters used in Ex.
Parameter
Value
Training steps
106
Start learn rate
10
End learn rate
10-5
Learn rate schedule
Exponential
Exponential decay rate
1.0
Number of random seeds
25
31

---

NeurIPS Paper Checklist
Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
The main claims made have been proved theoretically in detail in the appendix. Illustrative examples have also been shown to provide more clarity the ideas involved.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contri- butions made in the paper and important assumptions and limitations. No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The paper includes the limitations in the discussion section (Sec. 5).
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are vi- olations these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope the claims made, e.g., if the approach was only tested on few datasets with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover lim- itations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an important role in de- veloping norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
32

---

Justification: We provide the theoretical results in an organized manner with numbered and cross- referenced equations, theorems, lemmas, assumptions etc. We have considered the proof' in rigorous detail and explain all the details in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The information needed to reproduce the main experimental results of the paper disclosed in further detail in App. and App. H.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, the contribution is a novel architecture, describing the architecture fully might suffice, if the contribution is specific model and empirical evaluation, it may be essary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models. it may be that access to the model is limited in some way (c.g., to registered users), but should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
33

---

Question: Does the paper provide open access to the data and code, with sufficient instructions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We intend to make the code open access after the review process is complete.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https: httpss://niiapa cttplippp.cpppbbbae cc/publcc/
guides/Ce Sttpe//ooeSuubiiecc www.imissssioooiiiiioooooii for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed reproduce the results. See the NeurIPS code and data submission guidelines (https: for more details.
to
//nips. //nips.cc/publll http/pullggggudeeeeeooooop http://ooeeummmsssosiiioooe.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new pro- posed method and baselines. only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparame- ters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The main details are provided in the paper. Additional details are provided in the appendix (app. H).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental mate- rial.
Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance the experiments?
Answer: [Yes]
Justification: The example mentioned in the main text is run with 25 random seeds and the median and interquantile range are plotted.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars capturing should be clearly stated (for ample, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
34

---

The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce exper- iments?
Answer: [Yes]
Justification: The relevant information about compute resources provided in the appendix (App. H).
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual exper- imental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethies https://neuripps httpppbllce/ttaaccsoooeeeeeeeeee ines?
Answer: [Yes]
Justification: The research conducted in the paper conforms with every aspect of the NeurlPS Code of Ethies.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a devi- ation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consideration due to laws or regulations in their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts the work performed?
Answer: [NA]
Justification: The research conducted in this paper is foundational research that focuses on de- veloping theoretical results and as such, does not directly have a societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed. If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
35

---

The conference expects that many papers will be foundational research and not tied to par- ticular applications, let alone deployments. However, if there direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mecha- nisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer:[NA]
Justification: Since the paper is based on foundational research, does not pose any direct risks that require safeguarding.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with neces- sary safeguards allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use the package weerssiithhhdee should be provided. For popular datasets, paperswi thcode. com/ /ataattaetss has curated licenses for some datasets. Their licensing guide can help determine the license a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
36

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (TRB) Approvals or Equivalent for Research with Human Sub- jects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if ap- plicable), such the institution conducting the review.
37


Reviews:
[{"review_id": "T234Se3dqN", "reviewer": "Reviewer_6ZcU", "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.", "questions": "1. How does PASQL scale with the dimensionality of the state and action spaces in practical scenarios?\n2. On what basis were the specific periods chosen for the policies in the experiments, and how sensitive is PASQL's performance to these choices?", "limitations": "yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n2. The paper provides a rigorous theoretical framework, including convergence proofs and bounds on sub-optimality, which substantiates the claims made about PASQL's efficacy.\n3. Through numerical experiments, the paper effectively demonstrates that PASQL can outperform standard Q-learning in POMDP settings, offering practical relevance to the theoretical claims.\n4. 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.\n2. The current study focuses on tabular representations, which might not scale well to high-dimensional problems or those requiring function approximation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive endorsement. We address your questions and concerns.\n\n### **1. How does PASQL scale with the dimensionality of the state and action spaces in practical scenarios?**\n\nIn 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}$.\n\nThe scaling with respect to state and action spaces will remain similar to that of ASQL with a worst-case additional scaling factor of $L$. \nThere are two ways in which we can think about scaling in this setting: memory and sample complexity. \nFor 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. \n    \n### **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?**\n\nIn 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$.\n\nIt 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\ntake any integer sequence $\\lbrace L_n\\rbrace_{n\\ge1}$ that has the property that $L_n$ divides $L_{n+1}$, then the\nperformance of the policies with period $L_n$ is monotonically increasing in $n$. We will adapt the discussion around line 83 to clarify this point.", "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": "", "extra_scores": {}}, {"review_id": "rU2Q2utYFr", "reviewer": "Reviewer_4hWX", "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.  \nAn approach based on learning periodic policies using Q-learning is presented and convergence guarantees for this type of policies are presented under some assumptions. \nFinally, a numerical experiment validates the claims and the benefits of using the devised approach.", "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.\n\nIt 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?\n\nThe 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.  \n\nThe 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?  \nFurthermore, 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?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "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.  \n\nThe 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.\nAs 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.\n\nTheorem 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.\n\nIt 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. \n\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. We address your questions and concerns.\n\n### **1. Monotonically increasing performance of periodic policies**\nWe 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.\n\nSince $Π_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.\n\n    \n### **2. Non-Markov agent state $Z_t$**\n\nThe 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.\n\nLemma 1 is different from the fact that agent state is a controlled Markov process. The controlled Markov property states that\n\n$\\def\\PR{\\mathbb{P}}\\PR(z_{t+1}|z_{1:t},a_{1:t})=\\PR(z_{t+1}|z_t,a_t)$.\n\nwhile Lemma 1 states that\n\n$\\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).$\n\nThese two are different and the latter does not imply the former because the functions of Markov chains are not necessarily Markov. \n\n**Proof of Lemma 1**: Lemma 1 is an immediate consequence of the law of total probability, which implies that\n\n$\\def\\2{\\phantom{\\1}}\\def\\I{\\mathbb{1}}\n\\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})$\n\n$\\2=μ(a_{t+1}|z_{t+1}) \\I\\lbrace z_{t+1} = \\phi(z_t, y_{t+1}, a_t) \\rbrace\n\\PR(s_{t+1},y_{t+1}| s_t, a_t)$\n\n$\\2=\\PR(s_{t+1},z_{t+1},y_{t+1},a_{t+1} | s_{t}, z_{t}, y_{t}, a_{t})$.\n\n\n### **3.  Improvement over previous learning rates**\n\nWe 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\n\n$\\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},$\n\nwhereas 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$.\n\n    \n### **4. Periodic Markov chains and optimal policies**\n\nIt 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.\n\nThe 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.\n    \n### **5.  Weaker assumption of irreducibility and aperiodicity in periodic MC**\n\nLet $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.\n\nWhen $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.\n\n### **6. Comparison with [Sey+23]**\n\nWe 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].\n\n### **7. Claim regarding non-stationarity is confusing**\n\nPlease see the official comment below.", "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": "", "extra_scores": {}}, {"review_id": "x17VLK9sQ7", "reviewer": "Reviewer_6y9j", "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.\n\nI'm happy to strongly recommend acceptance.", "questions": "(As mentioned above:)\n\n1. Could you please comment on the relevance of the insights towards larger POMDPs, like those common in deep RL?\n2. In the numerical examples, is there an explanation for why $u_1$ is a better choice than $u_2$ and $u_3$? \n3. 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?", "limitations": "Yes.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "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.\n\n**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.\n\n**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. \n\n**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. \n\n**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.\n\nThe following is a list of limitations. These are mostly stated clearly in the paper and I don't think they constitute reasons to reject.\n- 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. \n- For the above reason, I'm not sure this particular algorithm will see practical use. \n- The choice of behavioural policy is critical.\n- The framing of the problem is limited to deterministic Q-learning. It does not consider stochastic or policy gradient methods. \n\n**Clarity**: A couple of minor issues: \n- 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$. \n- In the numerical examples, is there an explanation for why $u_1$ is a better choice than $u_2$ and $u_3$? \n\n**Significance**: See prior comments on practicality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and the positive endorsement. We address your questions and concerns below.\n\n### **1. Could you please comment on the relevance of the insights towards larger POMDPs, like those common in deep RL?**\n\nThe 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. \n\nAt 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.\n\n\n### **2. In the numerical examples, is there an explanation for why $u_1$ is a better choice than $u_2$ and $u_3$ ?**\n\nIt 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. \n\nIn 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.\n\n\n### **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?**\n\nTo address this, we will adapt the paragraph starting on line 42 as follows:\n\nWhen 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).\nIn 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 ...\n\n\n### **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.**\n\nThe 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.", "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": "", "extra_scores": {}}, {"review_id": "2VS3qLyH3N", "reviewer": "Reviewer_aMY6", "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.\nAs a consequence, the authors propose a special form of nonstationary policies that may be better suited for non-Markovian agent-states.", "questions": "Have you considered other non-stationary approaches?", "limitations": "The authors addressed the limitations adequately.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper has an interesting problem setting and describes well the limitations of stationary policies applied to non-Markovian agent-states.\n\n2. 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?\n\n2. 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.\n\n3. The numerical experiments consider only small examples.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback.\n\n### **1. Considering other non-stationary approaches**\n\nAs 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.\n\n### **2. The numerical experiments consider only small examples.**\n\nThe 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.\n\n### **3. Deterministic vs stochastic policies.**\n\nPlease see our response in the global 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": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for the comments and feedback. We address some of the common issues raised by the reviewers below.

### **1. Practical implementation of the algorithm**

We want to clarify certain points regarding the practical implementation of the algorithm. 

- In terms of implementation complexity, the deep RL version of the algorithm can be implemented with a shared LSTM/RSSM base (similar to R2D2 [Kap+19] / Dreamer [Haf+20]) and multiple heads corresponding to each $L$. So, the additional memory overhead of implementing the algorithm is not too restrictive. 

 - In terms of sample complexity, in the worst case the sample complexity will decrease by a factor of $L$, but in practice the sample complexity will not be so large because the function $Q^{\ell}$ is bootstrapped from $Q^{[[\ell+1]]}$. This is indeed the case in our current experiments where the sample complexity for $L=2$ (Fig 3) is roughly the same as $L=1$ (Fig 5).

 - In terms of performance, as we mention in the introduction, PASQL with period $m$ will perform at least as well as PASQL with period $n$ if $m$ is a multiple of $n$. Therefore, PASQL with any $L > 1$ would have performance which is at least as good as the performance of ASQL (which corresponds to $L=1$). Hence, one can think of $L$ as a hyper-parameter which is tuned with other hyper-parameters.


### **2. Deterministic vs Stochastic policies**

The main thesis of the paper is that non-stationary policies perform better than stationary policies in POMDPs with agent state. This is true for both deterministic and stochastic policies. For instance, as we point out on line 959 (page 22) that non-stationary deterministic policies (and therefore non-stationary stochastic policies) can in general perform better than stationary stochastic policies. Thus, adding non-stationarity is beneficial for both deterministic and stochastic policies.

 In this paper, we propose and analyze a variant of Q-learning that converges to a non-stationary policy. The reason that we focus on Q-learning is because the current state of the art RL algorithms for POMDPs such as R2D2 and Dreamer are variants of Q-learning. In principle, the same idea would work for actor-critic algorithms as well. In fact, our results provide a strong motivation that one should investigate periodic variants of actor-critic algorithms for POMDPs

### **3. Choice of the behavioral policy**

The converged value of any agent-state based Q-learning (ASQL) algorithm depends on the behavioral policy. This is in contrast to MDPs, where at least in theory, any behavioral policy works as long as all state action pairs are visited infinitely often. Even then, the behavior policy does impact the sample complexity of Q-learning, and there is a rich literature on choosing the behavior/exploration policy. Sucn an understanding does not exist for ASQL. Since our algorithm generalizes ASQL to learn non-stationary policies, it shares the same limitations as every Q-learning algorithm for POMDPs.

Meta-review: This paper presents a method for improving learning in POMDPs using period policies. It shows that in cases where the 'agent state' that is used for decision-making is imperfect (non-Markovian) non-stationary policies can outperform stationary ones. Periodic agent-state based Q-learning (PASQL) is proposed to learn a form of non-stationary policy that can converge. Experiments also show the method can work well. 

Learning in POMDPs is an important but hard topic. Developing better theory and algorithms for this case is a worthwhile challenge. This paper highlights an important problem with simpler methods that poorly approximate the belief or history and provide a rigorous solution. It also presents a proposed solution that is theoretically strong and performs well.  

While the theory is strong in this paper, the presentation is unclear at times due to the dense nature of the paper. For instance, the assumptions of the method are not fully clear in the current paper. First, the introduction of the paper seems to indicate that belief-state MDPs being the only 'correct' way to represent an 'agent state' when methods for learning history abstractions (e.g., using an RNN) could learn a Markovian agent state. Similarly, there is mention of 'memory augmentation' in the discussion but learning a better agent state may be easier. Second, some of the other assumptions are not clear. For example, it is not clear how restrictive Assumption 2 is. Other details are provided by the reviewers. There was also some uncertainty about how practical the proposed algorithm is. The author response was helpful for clarifying some of these points but the setting and assumptions should be clarified in the paper.
Decision: Accept (poster)