How memory architecture affects learning in a simple POMDP: the two-hypothesis testing problem
Authors: Mario Geiger
Christophe Eloy
Matthieu Wyart
Venue: ICLR 2022 Submitted (2022)
Keywords: POMDP
memory architecture
optimization
reinforcement learning

Abstract: Reinforcement learning is generally difficult for partially observable Markov decision processes (POMDPs), which occurs when the agent's observation is partial or noisy. To seek good performance in POMDPs, one strategy is to endow the agent with a finite memory, whose update is governed by the policy. However, policy optimization is non-convex in that case and can lead to poor training performance for random initialization. The performance can be empirically improved by constraining the memory architecture, then sacrificing optimality to facilitate training. Here we study this trade-off in a two-hypothesis testing problem, akin to the two-arm bandit problem. We compare two extreme cases: (i) the random access memory where any transitions between $M$ memory states are allowed and (ii) a fixed memory where the agent can access its last $m$ actions and rewards. For (i), the probability $q$ to play the worst arm is known to be exponentially small in $M$ for the optimal policy. Our main result is to show that similar performance can be reached for (ii) as well, despite the simplicity of the memory architecture: using a conjecture on Gray-ordered binary necklaces, we find policies for which $q$ is exponentially small in $2^m$, i.e. $q\sim\alpha^{2^m}$ with $\alpha < 1$. In addition, we observe empirically that training from random initialization leads to very poor results for (i), and significantly better results for (ii) thanks to the constraints on the memory architecture.

Under review as a conference paper at ICLR 2022
HOW MEMORY ARCHITECTURE AFFECTS LEARNING IN A SIMPLE POMDP: THE TWO-HYPOTHESIS TESTING PROBLEM
Anonymous authors Paper under double-blind review
ABSTRACT
Reinforcement learning is generally difficult for partially observable Markov de- cision processes (POMDPs), which occurs when the agent's observation is partial or noisy. To seek good performance in POMDPs, one strategy is to endow the agent with finite memory, whose update is governed by the policy. However, policy optimization is non-convex in that case and can lead to poor training per- formance for random initialization. The performance can be empirically improved by constraining the memory architecture, then sacrificing optimality to facilitate training. Here we study this trade-off in two-hypothesis testing problem, akin to the two-arm bandit problem. We compare two extreme cases: (i) the random access memory where any transitions between M memory states are allowed and (ii) fixed memory where the agent can access its last m actions and rewards. For (i), the probability to play the worst arm is known to be exponentially small M for the optimal policy. Our main result is to show that similar performance can be reached for (ii) as well, despite the simplicity of the memory architecture: using conjecture Gray-ordered binary necklaces, is exponentially small in 2m i.e. a with a < 1. In addition, we observe empirically that training from random initialization leads to very poor results for (i), and significantly better results for (ii) thanks to the constraints on the memory architecture.
find policies for which
INTRODUCTION
Reinforcement learning is aimed at finding the sequence of actions that should take an agent to maximise long-term reward (Sutton & Barto (2018). This sequential decision-making is usually modeled Markov decision process (MDP): at each time step, the agent chooses action based on a policy (a function that relates the agent's 's state to its action), with the aim of maximizing its value (the expected discounted sum of rewards). Deterministic optimal policies can be found through dynamic programming (Bellman (966)) when MDPs are discrete (both states and actions belong to discrete sets) and the agent fully knows environment (Watkins Dayan (192)).
A practical difficulty arises when the agent only have a partial observation of its environment or when this observation imperfect stochastic. The mathematical framework is then known as a partially observable Markov decision process (POMDP) (Smallwood & Sondik () In this framework, the agent's state is replaced by the agent's belief, which the probability distribution over all possible states. At each time step, the agent's 's belief can be updated through Bayesian inference to account for observations. In the belief space, the problem becomes fully observable again and the POMDP can thus be solved as "belief MDP". However, the dimension of the belief space is much larger than the state space and solving the belief MDP can be challenging in practical problems. Some approaches seek to resolve this difficulty by approximating of the belief and the value functions (Hauskrecht (2000); et al. (2005) Silver & Veness (2010); Somani et al. (201)) ), deep model-free reinforcement learning where the neural network is complemented with memory (Oh et al. (2016); Khan et al. (2017)) or a recurrency (Hausknecht & Stone (2015) Li et al.
2015)) to better approximate history-based policies.

---

Under review as a conference paper at ICLR 2022
(1993), who proposed to give the agent limited number of Here we focus on the idea of Littman
bits of memory, an idea that has been developed independently in the robotics community where is known finite-state controller (Meuleau et al. (199 2013)). These works show that adding a memory usually increases the performance in POMDPs. But to this day. attempts to find opti- mal memory allocation have been essentially empirical (Peshkin et al. (200T); Zhang et al. (20T6); Toro Icarte et al. (2020)) One central difficulty is that the value is a non-convex function of policy for POMDPs (Jakkoll et al. (1995)): learning will thus generally get stuck in poor local maxima for random policy initialization. This problem is even more acute when memory is large or when all transitions between memory states are allowed. To improve learning, restricting the policy space to specific memory architectures where most transitions are forbidden is key (Peshkin et al. (200T); Zhang et al. (2016); Toro lcarte et al. (2020). However, there is no general principles to optimize the memory architectures or the policy initialization. In fact, this question is not understood satisfyingly even in the simplest tasks- arguably a necessary step to later achieve a broad understanding.
Here, we work out how the memory architecture affects optimal solutions in perhaps the simplest POMDP, and find that these solutions are intriguingly complex. Specifically, we consider the two- hypothesis testing problem. At each time step, the agent chooses pull one of two arms that yield random rewards with different means. We compare two memory structures: (i) a random access memory (RAM) in which all possible transitions between M distinet memory states allowed; (ii) a Memento memory in which the agent can access its last m actions and rewards.
When the agent is provided with a RAM memory, we study the performance of a "column of confi- dence" policy (CCP): the agent keeps repeating the same action and updates its confidence in it by moving up and down the memory sites until it reaches the bottom of the column and the alternative action is tried. The performance of this policy is assessed through the calculation of the expected frequency q to play the worst arm (thus the smaller q. the better). For the CCP, q can be shown to be exponentially small in M. This result is closely related to the work of Hellman & Cover (1970) on hypothesis testing and its extension to finite horizon (Wilson) (2014)). learning a policy with RAM memory and random initialization leads to poor results, far from the performance of the column of confidence policy. Restricting memory transitions to chain-like transitions leads to much better results, although still sub-optimal.
practice, we find that
Our main findings concerns the Memento memory architecture. Surprisingly, despite the lack of flexibility of the memory structure, excellent policies exist. Specifically, using conjecture Gray- ordered binary necklaces (Degni & Drisko (007)) we find a policy for which q is exponentially small in 2 -which is considerably better than q In(m)/m, optimal for agent that only plays m times. For Memento memory, we also observe empirically that learning is faster and perform better than in the RAM case.
The code to reproduce the experiments is available at hattps://anonnnnt 4oppe. science/r/ter hww.thowyypphhhssseeeee BAB3 and uses function defined here httpps: // anonymous. 4open. wwwescceeeeeeeeeeeceec.c gradient flantfloww ow gradientflow The experiments where executed on CPUs for about 10 thousand CPU hours.
2 POMDPs AND THE TWO-HYPOTHESIS TESTING PROBLEM
2.1 GENERAL FORMULATION
Definition 2.1 (POMDP). A discrete-time POMDP model is defined as the 8-tuple (S, T, R, S2 O, Po. S is set of states, A is set of actions, T is conditional transition probability function T(s'|s, a) where s',8 s E S and a E A, R 5 + R is the reward function ! Ω is set of observations, Oooss) is conditional observation probability with o E Ω and E S. Po(s): : S + R is the probability to start in a given state s, and E [0, 1) is the discount factor.
A state s e S specifies everything about the world at a given time (the agent, its memory and all the rest). The agent starts its journey in state s E S with probability Po(s). Based on an observation o E obtained with probability Oooss) the agent takes an action a E A. This action causes a transition to the state s' with probability T(s'ls (s. a) and the agent gains the reward R(s). And so on.
R. Our notation is not loss of generality. The set of can he made higger S S in order contain the last action.
In the literature, R also depends the action: R: S x A +
2

---

Under review as a conference paper at ICLR 2022
Definition 2.2 (Policy). A policy r(alo) is conditional probability of executing action A given am observation 0 E Q.
Definition 2.3 (Policy State Transition), Given a policy the state transition TĄ is given by
(=(8'))
Σ T(*'(8, a((100)))((
0,aERXA
Definition 2.4 (Expected sum of discounted rewards). The expected sum of future discounted re- wards of a policy is
G = E
Σ ((s)))
(2)
So po
81 ~ Tx (-180)
1=0
92 T (-151)
Note that POMDP with expected sum of future discounted rewards with discount factor ry be reduced to an undiscounted POMDP (Altman 1999). ). as we now recall (see proof Appendix AA: undis-
Lemma 2.1. The discounted POMDP defined in 2.1 with discount Y is equivalent counted POMDP with a probability r = 7 to be reset from any state toward an initial state. In the undiscounted POMDP, the agent reaches steady state p(s) which can be used calculate the expected sum of discounted rewards G2 = [[s)]] [[(s]]
2.2 OPTIMIZATION ALGORITHM
To optimize policy algorithmically, we apply gradient descent on the expected sum of discounted rewards. First, we parametrize policy with parameters exp(#),e)
R|A @il, normalized get proba-
bility using the softmax function T. (a/o) = Σ, exp((xxa) Then, we compute the transition matrix
Tw, from which we obtain the steady state p using the power method (See Appendix Finally, we calculate Gz by the Lemma 2.1
Using an algorithm that keeps track of the operations (we use pytorch Paszke et al. (001) 7), we compute the gradient of G with respect the parameters and perform gradient descent with adaptive time steps (i.e. gradient flow dynamics):
w
dw Gw))..
(3)
dt
2.3 TWO-HYPOTHESIS TESTING PROBLEM
The problem we consider is the two-hypothesis testing problem. We label two arms by the letters A and B. The two arms gives reward of +1 or -1 with a Bernoulli distribution. The probabilities obtain positive reward are noted aA and kg respectively. The environment is entirely deñned by the couple (kA, kn). With equal probability, the environment is in one of the following two configurations (hypothesis):
{ kA = 1+
kB = 1-
(hypothesis HA)
kA = 1Sp
kB = 1fp (hypothesis HB)
(4)
where the hypothesis A (resp. HB) corresponds to A (resp. B) being the best arm. In expectation over the environments, an agent that plays randomly or always the same arm will have a reward O.
Note that this problem is similar to the Bandit problem, except that in the latter (k kn) can take any value in the square [0, 1]2. When r - O, our results below can be generalized to the bandit problem, done in Cover & Hellman (1970) by recasting the latter as finding the correct hypothesis 'Arm A is better or 'Arm B is better").
In setup, the agent only knows its last arm played, reward obtained (if there some) and the state its memory (different memories are described below). Based on that, it chooses an arm (play A or B) and how to update its memory state.
In the POMDP formalism (c.f. 2.1). the state s contains the environment (ka, kR), the memory state, the last played and reward obtained. We only consider agents that have complete access
3

---

Under review as a conference paper at ICLR 2022
to their memory, therefore O is deterministic and simply projects s by removing the environment
information.
environment A or HB), memory state, last arm played (A or B) and last reward (1 or -1)
0 memory state, last arm played and last reward
arm to play, memory update
(5) We define the function q(s), which is if the agent just played the "wrong" arm in state and 0 if he played the correct one. The probability to play the wrong arm then y = Ex--pl [[(()) where p is the steady state of the problem with reset r. The expected sum of discounted gains G can be
related to fnr as: G2- = (11 2qx). the following, we will use qx as measure of performance, trying to find policy π that minimizes qa (and thus maximizes G
2.4 TYPES OF MEMORY CONSIDERED
Definition 2.5 (Random Access Memory (RAM)). RAM is the most flexible memory setting. The agent has M memory states and has full control over it. has ||| M x 2 possible actions: the choice of the next memory state and which arm to play. There is high degeneracy in the space of strategies since any permutation of the memory states leads to the same performance. Note that, since agent can the information of the last arm and reward, the total number of memory states is in fact Mea = 4M, which corresponds to 2 + log, M bits.
Definition 2.6 (Memento MemoryD.. The agent only has access to the information of its past m actions and rewards. For instance, for = 4, an observation could be AABB-+-+, We use the notation of the most recent action/reward on the right (here, the last action was B and the reward was +1). If the agent plays A and obtains positive reward, the next memory state would be ABBA+ ++ In this memory architecture, the agent writes in its memory only through the plays he does (IAA 2). Here, the number of bits is 2m and the total number of memory states is in fact Mett = 4"
3 GAIN AND EXPLORATION WITH A RANDOM ACCESS MEMORY
Hellman & Cover 1970); Cover & Hellman 1970) described an optimal policy for the RAM ar- chitecture in the limit of a small reset r. their optimal policy, the memory states = 1...M are organized linearly with transitions only occurring between i and - 1 (if the last observation sup- ports A) or + 1 (if the last observation supports HB). In the limit r + 0, transition probabilities can be shown to be independent on i for 1 < i < M. The two extreme memory states i 1 and i i= M are special as they present a vanishing exit rate e + 0. Thus, only these two states are visited with finite probability in that limit. For such a policy, one obtains an optimal probability to play the worst arm (Hc(M) = a M-1 /aa + 1), with a = (1 /4) (1 +).
Our set-up slightly different, we allow for the choice of arm to depend on both the memory state and the information of the last arm played and reward obtained Tri In that case, the policy can be improved, demonstrated by considering the column of confidence policy.
Definition 3.1 (column of confidence policy (CCP).. It is RAM policy with M memory states. It is depicted in Figure TC. Essentially, the agent uses its last arm played to effectively increase the size of its memory by a factor 2.
The probability q to play the worst arm by following CCP is derived in Appendix for general r, by writing the transition probability matrix T. with a generic c, for any of the two hypotheses HA A or
Memento is Christopher Nolan's 's film where the hero has short-term memory loss every few minutes. Using photos and tattoos, the hero keeps track of information he will eventually forget, thus encoding informa- tion into his own actions.
'To see why linear policy is optimal, introduce X; P(H)))) ((HAA))/P(HHll) p() with ((Ha)() the conditional probability that HA true if the memory state i is visited. Chaose the labels i such that X 2 >2... 2 AM- Then it can be shown that d./As S -1 (Hellman Cover 1970)). The linear policy saturates this bound for all i, leading to the maximal ratio that can be obtained hetween any two states X1 /xx = o I-M This ratio where only these states visited with finite probabilities.
controls the gain in the limit
4

---

Under review as a conference paper at ICLR 2022
A Cover & Hellman
Cover & Hellman
1970 C
column of confidence policy:
Yn
en+1
In+1
8A
8B
y/
- - 4 with prob.
I
7A
7B
6A
6B
Ta
5A
+1
B Our setup:
y
-1
4A
4B
& play same arm
en-+
On+1
3A
3B
2A
2B
+1 + f 1 = change arm
Tn
n++1
1A
1B
y =
On
Qn
Op
Figure 1: Update scheme from Cover & Hellman (1970) vs our update scheme. Using the
same notation Cover & Hellman (970)) Yn is the reward obtained by playing the arm en and T, the memory state (not to confuse with the transition probability 7 Sec (.c To make the link with Sec 2.1 in our setup the state s, correspond the tuple (en, Un. Tn, k,, kB), the observation On to the triplet (en, Vn. I and the action an is represented by the purple and green arrows. The red arrow can be seen as part of the conditional probability [s,,-1|S2 an). C The column of confidence policy, that can be used in the RAM case, exemplified for M = 8. The memory states are organized into two columns. The distribution Po initializes the agent's memory into states 1A or B with equal chance. The agent keeps playing the same arm, moving up and down a column depending on the reward, unless it is in the memory state (it then switches arm after a negative reward). Once the agent reaches state at the top of column, it only step down with small probability if negative reward is obtained. This two-column arrangment effectively double the number of memory states, by creating 2M 16 distinct states. In this policy, the value of the memory can be viewed as a measure of the confidence the arm being played.
Hg. From the stationary distribution T.p p, one obtains q(c), which reaches its minimum value for:
a a (2 3) + a (2μ + 3) f 0(r)()
6= /2
(6)
v1 a M M a MM
The result /r indicates non-trivial balance between exploration and exploitation, in which the time spent in each extreme state of the memory grows only as the square root of the horizon time 1/r. A similar result obtained for hypothesis testing (Wilson (2014)).
For r - 0 (a result generalized for any kB and li in Appendix
we obtain:
2M-1
(ccr (M)
2M +1
Note that it is the optimal gain of a RAM memory of size 2M. Since our agent memory size is Men 4M (the factor 4 coming from the possible past actions and two possible rewards), the results of Hellman & Cover 1970 Cover & Hellman (9970) show that CCP is nearly optimal, in the sense that no policies with one less of memory can better. In Figure that it is at least local policy optimum, as performing policy optimization near this solution leads to no further improvements.
2 we confirm empirically
4 GAIN FOR MEMENTO MEMORY
Are there efficient policies when the agent memorizes the last arms played and rewards obtained (Memento memory cf. 2.6 the classical two-arm bandit problem, after a time m, the optimal strategy selects the worst with probability q O(In m/m) (Auer al. 2002)). It turns out that
5

---

Under review as a conference paper at ICLR 2022
10
10 10-2
10
Jr 0.1
M
H 0.1
10 6
J = 0.1
10
H 0.1
10
10
f = 0.1
M 20
/ 0.1
== 10
f = 0.2
M 5
μ 0.2
T= 10
10-
J 0.2
M 10
μ 0.2
== 10
μ 0.2
M 20
H 0.2
10
10
10-3
10
100
10
M
Figure 2: Left Probability to play the worst arm vs. the reset probability for different memory sizes M and two values of μ (the difference between the mean outcome of the arms). Right vs. memory size M for different r and indicated in legend. The solid lines show the analytical result corresponding column of confidence policy (CCP), whereas symbols show the results the learning algorithm (see Sec 2.2 for a RAM memory with policy initialized close to the predicted optimal column of confidence policy (mo R TCCP + 10-4). Learning does find strategies that perform better than the optimal column of confidence policy, even for large values of indicating that it is local optimum. this figure, error bars would be smaller than the symbols.
AAAB
AABA
AABB
BABB
ABBB
AAAA
BAAB
ABBA
BBBB
BAAA ABAA
BBAA
BBAB
BBBA
Figure 3: Necklace policy with memory of the m = 4 last arms played and rewards obtained (Me- mento memory cf. (2.6). Memory states organized into 3 (5 if we consider the two end states) cycles of arms played, called necklaces in combinatorics. The memory state also contains the re- wards obtained, but these are not explicitly shown here for the sake of readability. Most of time, the agent stays in the same necklace by playing the oldest action he remembers. Each necklace has inputs and 2 outputs states (some states be both input and output). The agent has finite probability to leave its current necklace only when the output state is maximally informative: all rewards
for and for move to the left, the opposite move to the right. Thicker arrows represent high probability transition (deterministic in some situations); dashed arrows repre- sent input/output transitions between necklaces; and thin arrows represent the small probabilities to leave the two end states.
our agent can use his own actions to encode events over time much longer than m. leading exponentially small in 2 in a stationary state with long horizon r -
Definition 4.1 (Necklace policy). The necklace policy is based on key ingredients (Figure
(i) Most of the time, the agent plays the oldest action in its memory (i.e. the arm played m actions before). Doing so, memorizes actions cycle inside binary necklaces of length m (in combinatorics, necklace is an equivalent class of character strings under cyclic rotation, here the strings of length m made of the letters A and B, hence binary). When m is prime, there are exactly N ((m) 2 + (2mh - 2)/m distinct necklaces. For any m, the number of necklaces can be derived from Pólya 1937 's enumeration theorem and is equal to N N(m) Eam p(d)2m/d, where oo is the Euler's totient function.
words

---

Under review as a conference paper at ICLR 2022
(ii) We provide Gray order the necklaces. It means that necklaces numbered and two successive necklaces can only differ by one letter. We order the necklaces from = for the necklace where all actions are A to r2(m) for the necklace where all actions are B. The necklace i i= (resp. i = n(m)) also corresponds to the maximum confidence in hypothesis Н (resp. HB)- In general, the longest possible chain of necklace, n(m), is unknown and less than the total number N (m) of necklaces. But, when m is prime, it has been conjectured (and checked for m S 37) that there exists a Gray order of all distinct necklaces (Degni & Drisko (2007) other words, + (2 2)/m, for m prime.
((m) = (mm)
(ii) The probability to exit necklace is zero, except for two exit configurations for which this probability is 61 > 0 if two conditions are met. First, the memorized actions must allow the agent to switch from the necklace to the necklace sequence of rewards must be maximally informative: to switch to the necklace i (i.e. gaining confidence A) all rewards have to be +1 for the arm and -1 for the arm and the opposite to switch to the necklace i + L.
1 or + by taking new action. Second, the
(iv) In the two extreme states, the probability of exit eo when all rewards are negative. Below, we consider the limit limes-o littee = g(Eo, t1) of this strategy. This order of limits ensures that only the extreme states are visited with a finite probability and that the agent cycles many times in each necklace before exit.
In order compute the optimal gain of the necklace policy introduce the following lemmas. Lemma 4.1. Assume a discrete random walk on a chain of sites indexed by with probabilities r; to step from to i + and I to step from to i - 1. Starting in site the probability to reach site j + 1 (iis) j) before site i is
P3-s3 = (1+
4 4+1
+ 4
-1
4
Ti
ni ret111
7i
Proof. The proof is developed in Appendix D.I
Lemma 4.2. Assume discrete random walk on a chain of 2 sites indexed by 0, 1,.1.... n (with probabilities F; to step to the right and 1 to the left). If ro cR and lut1 cL, the limit - 0, the probability to be site n + is
p(n + 1)
1+
(9)
T1
Proof. The proof is developed in Appendix D.2
Using these two lemma the following theorem can be proved.
Theorem 4.3. Consider the two-hypothesis problem described (4) in the limit of small reset
- O. The necklace policy described in Definition 4.1 with parameters (eo E1) has probability to play the worst arm satisfying q 2 q", with:
9' -²= a m(1 (m(l-m(m)))
with a = 1-#
(10)
1 1+
The optimal necklace policy converges to when < & <
Proof. The detailed proof is contained in Appendix D.3
Note At leading order q¹ 2 + o(a²") This is because the number of distinct necklaces (mm) only differs from 2+ (2 -2)/m at second order, and because we expect to find Gray orders within those distinct necklaces whose length only differ from ((m) at second order.

---

Under review as a conference paper at ICLR 2022
RAM .M = 10-a
Memento 3, 10"
Mett 64, 10
0.5
E
0.4
0.3
0.2
0.1
0.0
RAM random
Memento random
RAM linear
Memento random
RAM random
RAM columns
Memento cycles
CCP
RAM CCP
Memento necklace
necklace (r
RAM M 20, r = 10
Memento m = 4, = 10
Mar 256, 10
0.5
0.4
B
D
F
0.3
0.2
0.1
0.0
RAM random
Memento random
RAM linear
Memento random Memento cycles
RAM random
RAM columns
CCP
RAM CCP
Memento necklace
necklace (r 0)
10
103
10
10
10
10
10
103
10
t
t
Figure 4: Dynamics of the optimization algorithm for different initialization methods. Probability play the worse arm q vs. algorithm time (time defined in (3) for different seeds. 20 initialization seeds are shown in light color and the median is shown in solid color. The wall time is caped to 1 hour per optimization. A-B RAM with M 8 and M = 20, we compare the random initialization, linear initialization where the jumps in memory states initialized to be contiguous, the columns initialization corresponding to linear initialization with the extra constraint that the last action is repeated except for the memory state and the CCP initialization, very close to the column of confidence policy (i.e. To s TCCP + 10-1, a difference that explains why the red curves can decrease). C-D q vs. for the Memento memory initialization with the cycles initialization that repeats the oldest action, except if all the remembered plays correspond
3 and m 4. We compare the random
maximally informative event (during training a path between the cycles has to be learned) and the necklace where cu and 6 has to be learned. E-F vs. for randomly initialized policies. The values of m (3 and 4) and M (16 and 64) are chosen such that the total memory needed to perform these strategies Man is identical in each panel. The dashed line corresponds to calculation of q for the CCP and for the necklace policy (for which we only have a prediction for 0). In this figure μ 0.1.
5 POLICY OPTIMIZATION AND LOCAL MINIMA
To study empirically how learning depends on the memory architecture, we measure how the proba- bility (t) to play the worse arm after a training time depends on the initialization of policy. For the RAM memory,
find that random initialization (blue curves) leads to very poor results (panels A and B of Figure 4.. Results however improve when linear structure for memory states imposed (orange curves) and when the arms played are segregated the sides of that linear structure
8

---

Under review as a conference paper at ICLR 2022
to form two columns (green). However, even in that case, training does not converge towards the optimal column of confidence parameters, unless parameters are initialized near the optimal values (red curves).
By contrast, training with the Memento memory (consisting in the last m actions and rewards, cf. 2.6 appears less sensitive to initialization. As shown in the panel C and D of Figure initializing the policy randomly (blue) performs does not perform as well as initializing the policy with necklaces (orange), however the difference is not significant.
Although the RAM architecture is in principle more flexible (and in fact include Memento mem- ories), we find that, for random initialization, the Memento architecture leads to actually befter policies after training. The comparison is shown in panels E and F of Figure 4 where the two memory architectutes are compared keeping the effective memory size Mett constant. This find- ing emphasizes the need to constrain memory architecture, so as to obtain smoother optimization landscapes.
CONCLUSION
Policies
Memory scheme
Memento (cf. 2.6
RAM (cf. 2.5
Policy
necklace (cf. 4.1
CCP (cf. 3.1
Effective memory
Mott 4
Meff
Performance (q
1) as function of Meff
mml-n(mm)) a -2-2" 2 a m
a (2M-1)
~ a Mar
a Men//
more generally for A kB)
km AA
m
11kk I/kA-1
m(n(m))22) 22/2
kn 1/kg I/kA-1
M
I-RA
Table 1: Comparison of the performances of the necklace and CCP strategies in the limit + 0. As shown in the last line, the gain of these policies can be generalized to any distribution of the Bernoulli probabilities k and kn (but needs not be optimal then).
Our results are summarized in Table that compares the necklace policy (ef. 4.1) and the column of confidence policy (cf. (.1)). For each of these policies, we provide the optimal performance, reached the limit r - 0. We conjecture that these policies are the optimal ones for the Memento and RAM memory schemes respectively. Concerning the Memento memory, this conjecture is supported by the simulations shown Figure 3 the best numerical policies found for m 3 and m are in fact the necklace policy.
An interesting additional questions for the future is the generalization of these ideas to a broader set of tasks. The CCP appears well-suited for multiple hypotheses testing (Chandrasekaran & Laksh- manan (998);; Yakowitz et al. (1974)) where it would correspond to a "star" policy with a branch for each hypothesis. Classifying optimal policies for more complex hierarchical tasks, such those involved in navigation (Theocharous et al. (2004): Toussaint et al. (2008)), would have practical applications. Looking ahead, it would interesting understand if these ideas have applications to other approaches dealing with POMDPs, including recurrent networks (Li et al. (2015)) whose theoretical understanding remains very limited.
Finally, it is intriguing that for all memory structures studied, a linear organization of memory states appears be optimal. Despite the fact that our set-up is intrinsically digital, optimal policies ap- proach an analog memory architecture with a single degree of freedom: it corresponds to the position along the chain, and measures the relative belief of one hypothesis over the other. neuroscience, dominants models of decision making often present single analogue variable being updated by observations (Gold & Shadlen (007);; Rescorla & Wagner (1972).. It would be interesting to test experimentally, in situations where the environment change with small probability r between two distinct classes, animals stick to two extreme believes, and leave them for exploration with
some rate Vr.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Eitan Altman. Constrained Markov Decision Processes. Chapman and Hall/CRC, 1999.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235 256, 2002.
Richard Bellman. Dynamic programming. Science, 153(3731):34-37, 1966.
Balakrishnan Chandrasekaran and Kadathur Lakshmanan. Finite memory multiple hypothesis IEEE Transactions on Information
testing: Close-to-optimal schemes for bernoulli problems. Theory, 24(6):755-759, 1978.
Thomas M. Cover and Martin Hellman. The two-armed-bandif problem with time-invariant finite memory. IEEE Transactions Information Theory, 16(2):185-195, 1970. doi: 10.1 101119/TTT. 1970.1054427.
Christopher Degni and Arthur A. Drisko. Gray-ordered binary necklaces. the electronic journal of combinatorics, pp. R7-R7, 2007.
Joshua I. Gold and Michael N. Shadlen. The neural basis of decision making. Annual review of neuroscience, 30, 2007.
Matthew Hausknecht and Peter Stone. Deep recurrent q-learning for partially observable mdps. 2015.
arXiv preprint
Milos Hauskrecht. Value-function approximations for partially observable markov decision pro- cesses. Journal of artificial intelligence research, 13:33-94, 2000.
Martin E. Hellman and Thomas M. Cover. Learning with Finite Memory. The Annals of Mathemat- ical Statistics, 41(3):765-783 1970. ISSN 0003-4851.
Tommi Jaakkola, Satinder Singh, and Michael I. Jordan. Reinforcement learning algorithm for partially observable markov decision problems. Advances in neural information processing sys- tems, pp. 345-352, 1995.
Arbaaz Khan, Clark Zhang, Nikolay Atanasov, Konstantinos Karydis, Vijay Kumar, and Daniel D. Lee. Memory augmented control networks. arXiv preprint arXiv:1709.05706, 2017.
Xiujun Li, Lihong Li, Jianfeng Gao, Xiaodong He, Jianshu Chen, Li Deng, and Ji He. Recurrent reinforcement learning: a hybrid approach. arXiv preprint 1rXiv:1509.03444, 2015.
Michael L. Littman. An optimization-bai bassd categorization of reinforcement learning environments.
From animals animats, 2:262 270, 1993.
Nicolas Meuleau, Kee-Eung Kim, Leslie Pack Kaelbling, and Anthony R. Cassandra. Solv- ing pomdps by searching the space of finite policies. In Kathryn B. Laskey and Henri Prade (eds.), UAI '99; Proceedings of the Fifteenth Conference on Uncertainty in Artificial In- telligence, Stockhoim, Sweden, July 30 August 1, 1999, pp. 417-426. Morgan Kaufmann. 1999. URL Stwpariiille.oe334ppeeeeeeeeeede
jsp ?mmnu=
1 @asmu=26article
1d=15
Nicolas Meuleau, Leonid Peshkin, Kee-Eung Kim, and Leslie Pack Kaelbling. Learning finite-state controllers for partially observable environments. arXiv preprint 1xXiv:3301.62// 2013.
Junhyuk Oh, Valliappa Chockalingam, Honglak Lee, al. Control of memory, active perception, and action in minecraft. In International Conference Machine Learning, pp. 2790-2799.
PMLR, 2016.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Leter. Automatic differentiation in pytorch. 2017.
Leonid Peshkin, Nicolas Meuleau, and Leslie Kaelbling. Learning policies with external memory. arXiv preprint cs/1103003, 2001.
10

---

Under review as a conference paper at ICLR 2022
George Pólya.
Kombinatorische anzahlbestimmmngen für gruppen, graphen und chemische verbindungen. Acta mathematica, (8(1))145-254) 1937.
Robert A. Rescorla and Allan R. Wagner. A theory of Pavlovian conditioning: Variations in the
effectiveness of reinforcement and nonreinforcement, pp. 64-99. Appleton-Century-Cree 1972.
Nicholas Roy, Geoffrey Gordon, and Sebastian Thrun. Finding approximate pomdp solutions through belief compression. Journal of artificial intelligence research, 23:1-40 2005.
David Silver and Joel Veness. Monte-carlo planning in large pomdps. Neural Information Processing Systems, 2010.
Richard D. Smallwood and Edward Sondik. The optimal control of partially observable markov processes finite horizon. Operations research, 21(5):1011-108; 1973.
Adhiraj Somani, Nan Ye, David Hsu, and Wee Sun Lee. Despot: Online pomdp planning with regularization. In NIPS, volume 13, pp. 1772-1780, 2013.
Richard S. Sutton and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
Georgios Theocharous, Kevin Murphy, and Leslic Pack Kaelbling. Representing hierarchical pomdps as dbns for multi-scale robot localization. In IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA '04. 2004, volume 1, pp. 1045-1051. IEEE, 2004.
Rodrigo Toro Icarte, Richard Valenzano, Toryn Q. Klassen, Phillip Christoffersen, Amir- massoud Farahmand, and Sheila A. Mcllraith. The act of remembering: A study in partially observable reinforcement learning. arXiv:20/0.01553 [cs]. 2020.
Mare Toussaint, Laurent Charlin, and Pascal Poupart. Hierarchical pomdp controller optimization by likelihood maximization. In UAI, volume 24, pp. 562-570, 2008.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4)2279-25) 2927 1992.
Andrea Wilson. Bounded Memory and Biases in Information Processing. Econometrica, 82(6): 2257-2294, 2014. ISSN 1468-0262. doi: 10.3982/ECTA12188.
Sidney Yakowitz et al. Multiple hypothesis testing by finite memory algorithms. The Annals of Statistics, 2(2):323-336, 1974.
Marvin Zhang, Zoe McCarthy, Chelsea Finn, Sergey Levine, and Pieter Abbeel. Learning deep neural network policies with continuous memory states. In 2016 JEEE International Conference on Robotics and Automation (ICRA), pp. 520-527, 2016. doi: 10.1 10.1109//CRA.2211.77777777

---

Under review as a conference paper at ICLR 2022
Appendices
A
PROOF OF LEMMA 2.
Proof. The state transition matrix of the undiscounted POMDP is
Tx (s'(s) rpo(s') + + -1-11)1rp (1)))
(11)
The steady state p(s) has to be stable through T thus satisfying p(s') Σ (s) In the tensor form, it can be written r + =T Applying recursively this formula n times obtain:
n-1
p= = Σ (1- (1-
(12)
Translating it into expectation value expression obtain:
nn=
E Egep [[()] Bs, ~ Po
Σ ( (1-r))((())) + - (
(13)
for any function f and where T is understood as matrix-vector product (note that Txp + p). By replacing f by and by taking the limit n - co, for r = 1 - 7 we can identify [3] with (2). thus obtaining the Lemma 2.1
B IMPLEMENTATION DETAILS
To compute the steady state we use the power method algorithm: A
When we have multiple independent environments (by environment we mean subset of that the agent cannot escape with its actions), S is the disjoint union of these environments: S = Si + S2 + .... If po factorize as follow po = P(S.) for s Sü we can compute the steady state by computing those of each independent environments.
The initial state of the memory of the agent can be optimized by allowing gradient flow to modify specific part of po. It could mathematically be reformulated special actions done special initial states to initialize the memory.
Data: A transition matrix M
Result: The steady state while the columns of M differ (with given tolerance) do MM M:
end
return a column of M;
Algorithm 1: Power method
C EXACT COMPUTATION FOR COLUMN OF CONFIDENCE POLICY
The mathematica notebook is provided along with the code, the link in Section Here we compute the optimal value of e (that maximize the gain) given and μ..
First observe that the states (3B+, 1A-,... ...) can be arranged along line:
MA+ +
2A +
1A+
IB+
2
MB+
(14)
MA-
2A
1A
iB
2B
MB
where the probability transition only occurs between consecutive states.
12

---

Under review as a conference paper at ICLR 2022
If merge the = we have 2M states and compute their transition matrix without reset:
1
ckB
A
ekB
AA
kB
Q
(15)
KB
KA
O
kB
ck
where ha- = (1 + 2)/2 and kn (1 p)/2 Including the reset, the transition probability becomes
My = r) rJ:
(16)
where J is 1/2 in the two central states 1A and 1B.
The steady state p; is the solution of
Σ MaP, = = E(1-r)Q; -ig)ps =-
(17)
We can split this problem in 5 regions: the A border, the A bulk, the center, the B bulk, the B border. In the bulks the (17)
(1 (1-r) (--r)kBP--- Pt + (1 r)kapt+1
(18)
The solutions are of the form p; crw., + Czwi with
+ (1-r)(1+
Wi
(19)
To fix the coefficients Cj. 02 in the bulks we have equations:
the left border (two first lines of (17
two in the center, at the injection (two middle lines of 17
the right border (two last lines of 17
Solving these equations, we can compute the probability to play the wrong arm (B, assuming > 0).
w4 + w+)(1 w __) 2M (1
w (e 1))(w= -
+ +(w+ ++ w-) + (w_ w+ ) M (w_ w+ 1)((w_ 1) 1)( + w (e 1) + 2w 2
4 in this expression of q expressed r, a and KA, kB in function of w Optimizing q with respect to leads to
2w w (w? w- w_ (w) +e (w+ w-))
(20)
(w_ 1)w (w++ - 1) 1) (w_ () w- - w w- w
(w_ 1)(w 1)( ) 112M (w W+ 1)((ww)))) w
w 3M w²? + w w-) w+4
-(w4
w-)
+w wi+ (2w4 + w + w4 w- (7 + 2w + w² (2]((w+ 1))
- (w4 +t w
6 = (w_w+) -M
w=2 2 2M
w (w- - 1) w+)
(w_ [_---- w_ 1)
+ [w+ ++ w
2n 1+ 1+ w w+)
w
(21)
13

---

Under review as a conference paper at ICLR 2022
We can make the Taylor expansion of with respect
c= V V a
3M--- + a (2 - 3) + a2M (2 + 3)
/r O(r)
(22)
v1 a (1 a μ 22M11)
with
1-u
I+p
For M large, it converge quickly toward
2r
1 u + +
(23)
In the limit 0 we get
2M
q
2M 2M-
O(V))
(24)
D RANDOM WALK ALONG A CHAIN
D.1 PROBABILITY TO TRAVERSE THE CHAIN
1 (4 +n)
Ti
i
Figure 5: Markov chain
Consider a random walk on a chain of sites with probabilities r; to move from site to i 1 and 4 move from i 3-1 (Figure First, starting at site i, the walker visits the site j + 1 before the site - 1. Note that P.-+ only depends on {4e Ve and fra)k-r Note also that according to this definition P:++; 4,tr* We also define 4:_.
compute the probability P.-.j (with j) that,
Pir- as the probability to reach i before + 1 by starting in j. then we have P... = ा...
Starting in i, after one time step the walker is either (i) in i (with probability 4) and the probability reach j 1 before reaching
becomes null, (ii) still in (with probability 1 - (4, rx)) and the probability to each j + before - is still given by Pa-.j, (iii) + 1 (with probability rt). Once ini+1 there are two possibilities: either the walker never comes back to and reaches jaaeesjj - (with probability P++1-s), or it does (with probability - P.+1-.)) and it again has the same probability Pa-.y to reach j + before
Thus we have:
P (1 (4 r:)) + (P+1->5 + (1 Pr-1+))
(25)
The quantities that matter are p; = rr:((1 + T:). If we isolate Pi-aj to the h.h., we get
pi Pi+1-11
p.+j = 1- 1-p:(1 P4+1-))
(26)
Making the changes of variable X,,, = 1-Pi-i and x; = 1-th
(note that x; = li/r:) we obtain
ps
X1 = 1; + X141-45).
(27)
By repeating the formula we see that we get
X, क = = 35 + 2,54414422 + +...+ -.
EI
+
(28)
from which we can get P.-. by the inverse transformation
P3-ッ = (1 + 4 4+11
1
(29)
r. r141
14

---

Under review as a conference paper at ICLR 2022
D.2 CHAIN WITH FINAL STATES
Let us consider the same chain as above with finite length n such that sites are labelled from i = n. Now add a final state at each end of the chain (sites probabilities to leave the final states asymptotically small, of order c. More precisely, the probability to move from i to 1 is eft (we call A as is probability to go to the Right, although concerns the most left site) and the probability to move from + to is eL. These probability and the probabilities p(0) and p(n + 1) to be on the site O and n + 1 are related by a balance of the flow from 0 to n + 1:
and n + 1). We consider the
p(O)eRPI-n = p(n + 1)eLPIen.
(30)
In the limit O, the probabilities to be in the extreme states tends to 1 and we thus have p(0) 1 - p(n + 1). yielding
Pien
p(n + 1)
(1+
(31)
R PI PI
This result can be simplified using the equality
Pien 1 1
(32)
Pion 1 + I
to finally obtain the formula
p(n +1
1
(33)
D.3 CHAIN OF NECKLACES
To compute the gain of the necklace policy, the idea is to show that necklaces can be arranged on chain that
33
(see Figure 3)
For m prime, the number of non trivial necklaces is (2"h - 2)/m. m, the trivial necklaces being the two final states (i.e., the words AAA. AA and BBB. .B) Using the conjecture Degni & Drisko (2007), there is a Gray order on these necklaces when m prime. In other words, there a chain from one final state to the other that passes exactly once by each necklace, the difference between two successive necklaces being exactly one bit (i.e. a single A is changed into B or vice versa).
In any case (m prime or not), we call n(m) the length of the longest chain with Gray order. We call (m) the length of the smallest necklace in that longest chain (arguably the smallest prime factor of m).
necklace is characterized by the numbers a and of letters A and B in the m-long word, with = m. After at least one complete loop in the necklace (i.e. least y(m) actions), the probabilities to leave that necklace (when we are at the exit states) are
4 = h kk)) G1 - k
(34)
(35)
With the odds do at least one loop increasing c goes zero (mm) goes to co.
In the two final states, and again after one loop, the probabilities to leave are eg = cn(1 - kn)
and R c k.) We
the formula 333 (when ég < <1 1), in which the
15

---

Under review as a conference paper at ICLR 2022
product simplifies
4
((())
k kB) b.
(36)
Pi
(1 k4) am) b
i=1
Imlma (11/kB 1)48
(37)
I1 -2 (1//ki - 1)a
(1/kg - 1)25//
(38)
(L/ka 1)2,a
11/kB- -1 m(x(m))2)/2
n(m)
1/KA-1)
since
Σ
(a, + = m(n(m) - 2)
(39)
2=1
where a, and b, are the occurrences A and B in the necklace i. Inserting
39 into 33 and using the value of KA and kB given in (4) for hypothesis HA leads to
p(n + 1) = (1 a=((1-((m))
1-# 1 I+
with a
(40)
and p(0) can be obtained by changing i into -u or a into 1/a, by symmetry of the necklace policy. The probabilities under hypothesis HB are obtained by exchanging p(0) and p(n + 1), again by symmetry.
Under hypothesis HA (resp. Hg), the value p(n 1) (resp. p(0) corresponds to the probability g" to play the worst arm if the probabilities of the non-final necklaces are zero (which asymptotically true if 6o < (1). To reach q², also need 61 be asymptotically small in order guarantee least one loop in each necklace and ca has to be asymptotically larger than the reset r. In summary, need 60 C1 < 1 to reach asymptotically q" otherwise the probability q will be larger than q"
D.4 COLUMN OF CONFIDENEE POLICY WITH NO RESET
When there no reset r we can compute the performance of the column of confidence policy for two arms of probabilities kA and kB. We obtain via (33) (assuming KA kB)
1 KB
1/kB -
M-1
(41)
KΛ
I/kA -
16


Reviews:
[{"review_id": "oxhONg98Kpb", "reviewer": "Reviewer_PEeX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "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": "", "main_review": "The problem studied in the paper is quite a bit of interest for strategy learning and synthesis for POMDPs where, unlike MDPs, memory is known to be essential. \n\nWhile the methodology in the paper is rigorous and explained well, the scope is very narrow to derive any general insight. The comparison is limited to a single problem. \n\nWhile the results are stated relatively carefully, there is room for improvement and better precision. For example, what is the meaning of \"<<\" in Theorem 4.3?\n\nMemory in POMDPs has attracted interest in neighboring contexts and from a different perspective in RL recently. The paper seems to be missing that literature. \nhttps://arxiv.org/pdf/2007.08351.pdf \nhttps://arxiv.org/pdf/2009.11459.pdf\nhttps://arxiv.org/abs/2105.14073", "summary_of_the_paper": "The paper compares two memory structures for policies for POMDPs through theoretical and empirical analysis in a relatively simple problem.", "summary_of_the_review": "An interesting yet very limited paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "dvN9wErhQvq", "reviewer": "Reviewer_7ywF", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "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": "", "main_review": "First, even though the ideas in this paper are fairly intuitive, I admit I found this paper very hard to read. Many of the explanations are not clear and the overall writing can be substantially improved.\n\nThe main novelty, in my opinion, is the presentation of the Gray-ordered necklaces, which I find to be very nice and quite original (while the CCP policy is well studied). However, the theoretical analysis of this structure is lacking, in the sense that the authors only analyzed this specific structure, but gave no theoretical guarantees on its optimality in the class of the Memento-based memories. At most, the authors conjecture optimality based on simulations that might only imply a local optimum. From a practical perspective, I think that this idea does not scale. First, it's not clear how to scale it to more than two arms, nor to non-binary rewards. Second, as a concept, playing actions in a cyclic manner can be disastrous in dynamic environments, so the usefulness of this idea beyond bandit problems is unclear.\n\nMoreover, the connection of the analyzed model to general POMDPs is a bit artificial, and I don't really see what insights the paper gives on memory architectures in POMDP. If I understand correctly, the claim is that Memento works better than RAM with random initialization, even though some RAM structures are better than Memento. This claim is mainly based on the empirical evaluation, and for it to be meaningful, it should be methodologically tested on various POMDP of different characteristics (e.g., such that require long/short memory, fast/slow mixing, etc.). Moreover, the application of both memory architectures is somewhat naive, and as both were extensively studied, I think that this does not suffice to prove this claim.\n\nOther comments\n- p.g. 2 - \"the value is a non-convex function of policy for POMDPs... This problem is even more acute when memory is large or when\nall transitions between memory states are allowed\" - please refrain from such comments. The value in nonconvex in the policy also in MDPs, but it is still possible to find an optimal solution - it's all about the structure of the problem and the chosen representation, so using it to claim that 'more memory is bad' is not really meaningful. For example - what if some RAM structure effectively reconstructs the real state?\n- POMDP formulation - the formulation in this paper feels very tailored for the specific problem and algorithms, but it's not the standard formulation. Specifically, it's not very natural to put the memory state inside the state representation - the memory is a characteristic of the policy, not of the environment, and for some representations, it unnecessarily increases the environment exponentially. \n- Honestly, I didn't understand section 2.2 and the related appendix (B). Please improve the explanations and add more details about how you calculate everything.\n- In Fig. 4, right column, it seems like the RAM-random option did not converge yet - does it converge to a worse value or just converge more slowly?", "summary_of_the_paper": "This paper tackles a two-armed bandit problem (of means $Ber(1/2+\\mu)$ and $Ber(1/2-\\mu)$, respectively) when memory is limited. Specifically, they model this problem as a POMDP (or, alternatively, hypothesis testing), where the hidden state determines the mean of each arm. The author claim that this simple model might provide some insights on memory architecture in general POMDPs (namely, how the history representation affects the learning process). The authors describe two memory architectures:\n\n(i) A general finite-state machine ('RAM'), which transitions based on the played arm and its reward. Specifically, they focus on the column of confidence policy (CCP). The memory structure - a chain where each end of the chain represents an arm. $+1$ reward moves the state towards an arm and $-1$ moves it away, except for the end states that have low escape probability. The policy - playing the arm that its end-state closer to the current state. \n\n(ii) History is presented as a memory buffer with the last arm plays and their rewards('Memento'). In this case, the authors present a policy that plays the same action sequence cyclically ('necklaces'). These cycles are chained in a Gray-ordering and the policy moves between cycles (change one action) only if a full cycle indicates that this switch is beneficial.\n\nThe authors analyze the (stationary) probability of playing the worse actions and show that the RAM model enjoys better (lower) probability. Finally, the authors try to learn a policy when relying on either RAM or Memento architectures. They showed that a random initialization, the Memento memory performs better, while imposing structural constraints that correspond with the suggested policies in (i) and (ii) make RAM memory perform better.", "summary_of_the_review": "The paper presents an interesting algorithm for two-armed bandit problems with finite history, but the ideas do not scale up to larger problems, and the empirical evaluation is not enough to draw any conclusion on more general POMDPs.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ZTW6uq3SM9", "reviewer": "Reviewer_42t7", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "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": "", "main_review": "How memory structure affects POMDP learning is very interesting, and it could be useful for future design of learning algorithm under uncertainties. But the paper only focuses on a very simple problem with two possible hypotheses for the unknown POMDP model. Though  insights gained from studying a simple problem could be useful for general problems, the paper doesn't provide discussion on how the ideas from the simple problem could be applied in general problems. Given the policy and analysis for the simple two-hypothesis problem, is there any insight which could be useful for the general problem? Could an agent with RAM or memento memory in a general problem learn the unknown parameter with some simulations? Any feature of the proposed policies may be extended to general POMDP problems? \n\nFor the simple two-armed problem, two memory structures are considered: random access memory and memento memory. For each memory structure, one policy is proposed with performance analysis. The proposed policy itself is not particularly novel since they are  available in the literature. The analysis is limited that the provided performance results are only in the asymptotic region when the discount factor converges to one. Given that the analysis focuses on the limit when the discount factor approaches one, why not considering the average performance formulation? Another import analysis would be the performance of the algorithm in a finite time horizon. Would it be possible to have some finite time performance analysis?\n\nThere are also some issues in the presentation and lack of details. Section 3 states that empirical results for local search are shown in Figure 2; however, Figure 2 only shows the results under different mu and r, and no results for the suggested local optimization. For policy optimization with different initialization schemes, there is no details on how each initialization scheme is implemented. Are the memory schemes only different in their initialization or actually different in their update dynamics? Is the same learning algorithm is used with different memory initialization or different policies are used to adapted to the memory structure?", "summary_of_the_paper": "The paper attempts to investigate how memory architecture affects learning performance of POMDP agents. It focuses on a very simple two-arm bandit problem with two hypotheses for their probabilities. Two memory structures are considered: random access memory and memento memory. For each memory structure, one policy is provided with a kind of asymptotic optimal performance. Simulation results for simple gradient based learning algorithms are shown under the two memory structures. ", "summary_of_the_review": "The considered problem is a bit too simple to have meaningful insights, and the paper provides almost no discussion on how the analysis on this simple problem could be useful for general POMDP problems. Even for the simple problem setting, the paper doesn't have performance guarantees for the proposed policy in the non-asymptotic region. \n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "NbtZAZt8TpZ", "reviewer": "Reviewer_BH7m", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "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": "", "main_review": "Strengths:\n\n1. The work is in an interesting direction and points out potential issues with current empirical approaches to learning memory allocations.\n\n2. The explanation of optimal policies (such as the necklace policy) and their proofs were well-done and insightful.\n\nWeaknesses:\n\n1. While the authors cite shortcomings in recent works when it comes to learning memory allocations, it would be nice to see the ideas explored here scaled up to similar-sized problems. If the principle of \"restricted memory architectures are easier to learn with and more robust to random initializations\" is true, this should be testable in larger and more complex POMDP's (and policies) even without knowing the optimal policies. \n\nA simple/naive way to do this would be to compare something like RNN's to something like an attention-based architecture that can only observe its last m interactions with the environment (or any other restrictive memory architecture). These could be trained with reinforcement learning in a visual navigation environment, for example. The size of m or the recurrent state could then be played with. \n\nPerforming experiments like this would not be particularly difficult and would easily make the insights of the paper applicable to modern techniques. \n", "summary_of_the_paper": "The authors compare two different memory architectures for the two-hypothesis testing problem. They show that a simple fixed memory where the agent can only access the previous m environment interactions is more robust to random initializations than a more flexible RAM-setup while still maintaining similar performance.", "summary_of_the_review": "This work points out potential issues with current empirical approaches to learning memory allocations and suggests that restricted memory architectures could be easier to use. While the authors do show this to be the case in one very simple environment, they do not show that this concept scales to other larger or more complex environments, such as visual navigation, that are currently used. As-is, the work is simply too narrow in scope and experiments to be a significant contribution to modern techniques and understanding.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agreed that the contribution is too limited for the paper to be published. I encourage the authors to take the reviews into account when improving their work.
Decision: Reject