## 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 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 ∼_ _α[2][m]_ with α < 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.

1 INTRODUCTION

Reinforcement learning is aimed at finding the sequence of actions that should take an agent to
maximise a long-term reward (Sutton & Barto (2018)). This sequential decision-making is usually
modeled as a Markov decision process (MDP): at each time step, the agent chooses an action based
on a policy (a function that relates the agent’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 (1966)) when MDPs are discrete (both states and actions belong to
discrete sets) and the agent fully knows its environment (Watkins & Dayan (1992)).

A practical difficulty arises when the agent only have a partial observation of its environment or
when this observation is imperfect or stochastic. The mathematical framework is then known as
a partially observable Markov decision process (POMDP) (Smallwood & Sondik (1973)). In this
framework, the agent’s state is replaced by the agent’s belief, which is the probability distribution
over all possible states. At each time step, the agent’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 a “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); Roy et al. (2005); Silver & Veness (2010); Somani et al. (2013)),
or use deep model-free reinforcement learning where the neural network is complemented with a
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.


-----

Here we focus on the idea of Littman (1993), who proposed to give the agent a limited number of
bits of memory, an idea that has been developed independently in the robotics community where it
is known as a finite-state controller (Meuleau et al. (1999; 2013)). These works show that adding
a memory usually increases the performance in POMDPs. But to this day, attempts to find optimal memory allocation have been essentially empirical (Peshkin et al. (2001); Zhang et al. (2016);
Toro Icarte et al. (2020)). One central difficulty is that the value is a non-convex function of policy
for POMDPs (Jaakkola 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. (2001);
Zhang et al. (2016); Toro Icarte 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 twohypothesis testing problem. At each time step, the agent chooses to 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 distinct memory states are 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 confidence” 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)). In practice, we find that
learning a policy with a 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.

Our main findings concerns the Memento memory architecture. Surprisingly, despite the lack of
flexibility of the memory structure, excellent policies exist. Specifically, using a conjecture on Grayordered binary necklaces (Degni & Drisko (2007)), we find a policy for which q is exponentially
small in 2[m] —which is considerably better than q ∼ ln(m)/m, optimal for an 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 https://anonymous.4open.](https://anonymous.4open.science/r/two-hypothesis-BAB3)
[science/r/two-hypothesis-BAB3,](https://anonymous.4open.science/r/two-hypothesis-BAB3) [and uses a function defined here https://](https://anonymous.4open.science/r/gradientflow/gradientflow)
[anonymous.4open.science/r/gradientflow/gradientflow.](https://anonymous.4open.science/r/gradientflow/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, A, T, R, Ω, O, p0, γ): S is a set of states, A is a set of actions, T is a conditional transition
probability function T (s[′]|s, a) where s[′], s ∈ _S and a ∈_ _A, R : S →_ R is the reward function[1],
Ω is a set of observations, O(o|s) is a conditional observation probability with o ∈ Ω and s ∈ _S,_
_p0(s) : S →_ R is the probability to start in a given state s, and γ ∈ [0, 1) is the discount factor.

A state s ∈ _S specifies everything about the world at a given time (the agent, its memory and all the_
rest). The agent starts its journey in a state s _S with probability p0(s). Based on an observation_
_∈_
_o ∈_ Ω obtained with probability O(o|s) the agent takes an action a ∈ _A. This action causes a_
transition to the state s[′] with probability T (s[′]|s, a) and the agent gains the reward R(s). And so on.

1In the literature, R also depends on the action: R : S × A → R. Our notation is not a loss of generality.
The set of state can be made bigger S → _S × A in order to contain the last action._


-----

**Definition 2.2 (Policy). A policy π(a|o) is a conditional probability of executing an action a ∈** _A_
given an observation o ∈ Ω.
**Definition 2.3 (Policy State Transition). Given a policy π, the state transition Tπ is given by**

_Tπ(s[′]_ _s) =_ _T_ (s[′] _s, a)π(a_ _o)O(o_ _s)._ (1)
_|_ _|_ _|_ _|_

_o,aX∈Ω×A_

**Definition 2.4 (Expected sum of discounted rewards). The expected sum of future discounted re-**
wards of a policy π is

_∞_

_Gπ = E s0_ _p0_ _γ[t]R(st)_ _._ (2)
_s1 ∼_ _Tπ(_ _s0)_ "Xt=0 #
_s2 ∼_ _Tπ(·|s1)_
_. . . ∼_ _·|_

Note that a POMDP with an expected sum of future discounted rewards with discount factor γ can be
reduced to an undiscounted POMDP (Altman (1999)), as we now recall (see proof in Appendix A):
**Lemma 2.1. The discounted POMDP defined in 2.1 with a discount γ is equivalent to an undis-**
_counted POMDP with a probability r = 1 −_ _γ to be reset from any state toward an initial state. In_
_the undiscounted POMDP, the agent reaches a steady state p(s) which can be used to calculate the_
_expected sum of discounted rewards Gπ =_ [1]r [E][s][∼][p][[][R][(][s][)]][.]

2.2 OPTIMIZATION ALGORITHM


To optimize a policy algorithmically, we apply gradient descent on the expected sum of discounted
rewards. First, we parametrize a policy with parametersbility using the softmax function πw(a _o) =_ exp(wao) _w ∈_ R[|][A][|×|][Ω][|], normalized to get a proba_|_ _b_ [exp(][w][bo][)] [. Then, we compute the transition matrix]

_T˜π, from which we obtain the steady state p using the power method (See Appendix B). Finally, weP_
calculate Gπ by the Lemma 2.1.

Using an algorithm that keeps track of the operations (we use pytorch Paszke et al. (2017)), we
can compute the gradient of Gπ with respect to the parameters w and perform gradient descent with
adaptive time steps (i.e. a gradient flow dynamics):
_d_

(3)

_dt_ _[w][ =][ d]dw_ _[G][π][(][w][)][.]_

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 a reward of +1 or −1 with a Bernoulli distribution. The probabilities
to obtain a positive reward are noted kA and kB respectively. The environment is entirely defined
by the couple (kA, kB). With equal probability, the environment is in one of the following two
configurations (hypothesis):
_kA =_ [1+]2[µ] _kB =_ [1][−]2[µ] (hypothesis HA) (4)

_kA =_ [1][−]2[µ] _kB =_ [1+]2[µ] (hypothesis HB)



where the hypothesis HA (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 0.

Note that this problem is similar to the Bandit problem, except that in the latter (kA, kB) can take any
value in the square [0, 1][2]. When r → 0, our results below can be generalized to the bandit problem,
as done in Cover & Hellman (1970) by recasting the latter as finding the correct hypothesis ( ‘Arm
A is better’ or ‘Arm B is better’).

In our setup, the agent only knows its last arm played, reward obtained (if there were some) and the
state of 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, kB), the memory
state, the last arm played and reward obtained. We only consider agents that have a complete access


-----

to their memory, therefore O is deterministic and simply projects s by removing the environment
information.

_s = environment HA or HB), memory state, last arm played (A or B) and last reward (1 or −1)_
_o = memory state, last arm played and last reward_
_a = arm to play, memory update_
(5)

We define the function q(s), which is 1 if the agent just played the ”wrong” arm in state s, and 0 if
he played the correct one. The probability to play the wrong arm is then qπ = Es _p[q(s)] where_
_∼_
_p is the steady state of the problem with reset r. The expected sum of discounted gains Gπ can be_
related to qπ as: Gπ = _[µ]r_ [(1][ −] [2][q][π][)][. In the following, we will use][ q][π][ as a measure of performance,]

trying to find a policy π that minimizes qπ (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. It has |A| = M × 2 possible actions: the
choice of the next memory state and which arm to play. There is a high degeneracy in the space
of strategies since any permutation of the memory states leads to the same performance. Note that,
since our agent can use the information of the last arm and reward, the total number of memory
states is in fact Meff = 4M, which corresponds to 2 + log2 M bits.

**Definition 2.6 (Memento Memory[2]). The agent only has access to the information of its past m**
actions and rewards. For instance, for m = 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 a 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 (|A| = 2). Here, the number of bits is 2m and the total number of memory states is in fact
_Meff = 4[m]._

3 GAIN AND EXPLORATION WITH A RANDOM ACCESS MEMORY

Hellman & Cover (1970); Cover & Hellman (1970) described an optimal policy for the RAM architecture in the limit of a small reset r. In their optimal policy, the memory states i = 1...M are
organized linearly with transitions only occurring between i and i − 1 (if the last observation supports HA) or i + 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 = M are special as they present a vanishing exit rate ϵ →_ 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 qHC(M ) = α[M] _[−][1]/(α[M]_ _[−][1]_ + 1), with α = (1 _µ)/(1 + µ)._ [3]
_−_

Our set-up is slightly different, as 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 (Figure 1A-B). In that case, the
policy can be improved, as demonstrated by considering the column of confidence policy.

**Definition 3.1 (column of confidence policy (CCP)). It is a RAM policy with M memory states. It**
is depicted in Figure 1C. 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 C for general r,
by writing the transition probability matrix Tϵ with a generic ϵ, for any of the two hypotheses HA or

2Memento is a Christopher Nolan’s film where the hero has a short-term memory loss every few minutes.
Using photos and tattoos, the hero keeps track of information he will eventually forget, thus encoding information into his own actions.
3To see why a linear policy is optimal, introduce λi = P (HA|i)/P (HB|i), with P (HA|i) the conditional
probability thatThen it can be shown that HA is true if the memory state λi/λi+1 ≤ _α[−][1]_ (Hellman & Cover (1970)). The linear policy saturates this bound i is visited. Choose the labels i such that λ1 ≥ _λ2... ≥_ _λM_ .
for all i, leading to the maximal ratio that can be obtained between any two states λ1/λM = α[1][−][M] . This ratio
controls the gain in the limit ϵ → 0 where only these two states are visited with finite probabilities.


-----

Cover & Hellman Cover & Hellman (1970):

_en_ _yn_ _en+1_ _yn+1_

_Tn−1_ _Tn_

**B** Our setup:

_en_ _yn_ _en+1_ _yn+1_

_Tn_ _Tn+1_


_on_ _an_ _on+1_


column of confidence policy:


8A 8B

7A 7B

6A 6B

5A 5B

4A 4B

3A 3B

2A 2B

1A 1B


_y = −1 ⇒↓_ with prob. ϵ

+1
_y =_ _⇒↑_
1
 _−_ _⇒↓_

& play same arm

+1
_y =_ _⇒↑_
1 change arm
 _−_ _⇒_


Figure 1: **A Update scheme from Cover & Hellman (1970) vs B our update scheme. Using the**
same notation as Cover & Hellman (1970), yn is the reward obtained by playing the arm en and Tn
is the memory state (not to confuse with the transition probability T of Sec 2.1). To make the link
with Sec 2.1 in our setup the state sn correspond to the tuple (en, yn, Tn, kA, kB), the observation
_on to the triplet (en, yn, Tn) and the action an is represented by the purple and green arrows. The_
red arrow can be seen as part of the conditional probability T (sn+1|sn, 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 p0 initializes the agent’s memory into states 1A
or 1B 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 1 (it then switches arm after a negative
reward). Once the agent reaches a state at the top of a column, it can only step down with small
probability ϵ if a 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 in the arm being played.

_HB. From the stationary distribution Tϵp⃗ = ⃗p, one obtains q(ϵ), which reaches its minimum value_
for:

_ϵ =_ _√2_ _α −_ _√α[3]1[M]_ _[−][1]α[M]+ α(1[M]_ (2αµ[M] − 3) +µ _αα[2][M][M]µ(2)_ _µ + 3)_ _√r + O(r)_ (6)

p

_−_ _−_ _−_ _−_

The result ϵ ∼ _[√]r indicates a 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 was obtained for hypothesis testing (Wilson (2014)).


For r → 0 (a result generalized for any kB and kA in Appendix C), we obtain:

_α[2][M]_ _[−][1]_
_qCCP(M_ ) = (7)

_α[2][M]_ _[−][1]_ + 1 _[.]_

Note that it is the optimal gain of a RAM memory of size 2M . Since our agent memory size is
_Meff = 4M (the factor 4 coming from the 2 possible past actions and two possible rewards), the_
results of Hellman & Cover (1970); Cover & Hellman (1970) show that CCP is nearly optimal, in the
sense that no policies with one less bit of memory can do better. In Figure 2, we confirm empirically
that it is at least a local policy optimum, as performing policy optimization near this solution leads
to no further improvements.

4 GAIN FOR MEMENTO MEMORY

Are there efficient policies when the agent memorizes the last m arms played and rewards obtained
(Memento memory cf. 2.6)? In the classical two-arm bandit problem, after a time m, the optimal
strategy selects the worst arm with probability q = O(ln m/m) (Auer et al. (2002)). It turns out that


-----

10[−][1]

10[−][2]

10[−][3]

10[−][4]

10[−][5]

|Col1|µ = 0.1 M = 5 µ = 0.1 M = 10 µ = 0.1 M = 20 µ = 0.2 M = 5 µ = 0.2 M = 10 µ = 0.2 M = 20|Col3|
|---|---|---|
||||

|µ = 0.1 r = 10−6 µ = 0.1 r = 10−4 µ = 0.1 r = 10−2 µ = 0.2 r = 10−6 µ = 0.2 r = 10−4 µ = 0.2 r = 10−2|Col2|
|---|---|
|||


10[−][5] 10[−][3] 10[−][1]


10[0] 10[1]


Figure 2: Left Probability to play the worst arm q vs. the reset probability r for different memory
sizes M and two values of µ (the difference between the mean outcome of the two arms). Right q
_vs. memory size M for different r and µ indicated in legend. The solid lines show the analytical_
result corresponding to column of confidence policy (CCP), whereas symbols show the results of the
learning algorithm (see Sec 2.2) for a RAM memory with a policy initialized close to the predicted
perform better than the optimal column of confidence policy, even for large values ofoptimal column of confidence policy (π0 ≈ _πCCP + 10[−][4]). Learning does not find strategies that r, indicating_
that it is a local optimum. In this figure, error bars would be smaller than the symbols.

Figure 3: Necklace policy with memory of the m = 4 last arms played and rewards obtained (Memento memory cf. 2.6). Memory states are 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 rewards 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 2 inputs and 2 outputs states (some states can be both input and output). The agent has a finite
probability to leave its current necklace only when the output state is maximally informative: all 4
rewards are + for A and − for B to move to the left, or the opposite to move to the right. Thicker
arrows represent high probability transition (deterministic in some situations); dashed arrows represent 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 a time much longer than m, leading to q
exponentially small in 2[m] in a stationary state with long horizon r → 0.

**Definition 4.1 (Necklace policy). The necklace policy is based on 4 key ingredients (Figure 3).**

(i) Most of the time, the agent plays the oldest action in its memory (i.e. the arm played m actions
before). Doing so, it memorizes actions cycle inside binary necklaces of length m (in combinatorics,
a necklace is an equivalent class of character strings under cyclic rotation, here the strings are words
of length m made of the letters A and B, hence binary). When m is prime, there are exactly N (m) =
2 + (2(1937)’s enumeration theorem and is equal to[m] _−_ 2)/m distinct necklaces. For any m N, the number of necklaces can be derived from P´(m) = _m1_ _d_ _m_ _[ϕ][(][d][)2][m/d][, where][ ϕ][ is the Euler’s]olya_

_|_
totient function.

P


-----

(ii) We provide a Gray order on the necklaces. It means that necklaces are numbered and two
successive necklaces can only differ by one letter. We order the necklaces from i = 1 for the
necklace where all actions are A to i = n(m) for the necklace where all actions are B. The necklace
_i = 1 (resp. i = n(m)) also corresponds to the maximum confidence in hypothesis HA (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 ≤ 37)
that there exists a Gray order of all distinct necklaces (Degni & Drisko (2007)): in other words,
_n(m) = N_ (m) = 2 + (2[m] _−_ 2)/m, for m prime.

(iii) The probability to exit a necklace is zero, except for two exit configurations for which this
probability is ϵ1 > 0 if two conditions are met. First, the memorized actions must allow the agent
to switch from the necklace i to the necklace i − 1 or i + 1 by taking a new action. Second, the
sequence of rewards must be maximally informative: to switch to the necklace i − 1 (i.e. gaining
confidence in HA), all rewards have to be +1 for the arm A and 1 for the arm B and the opposite
_−_
to switch to the necklace i + 1.

(iv) In the two extreme states, the probability of exit is ϵ0 when all rewards are negative. Below, we
consider the limit limϵ1 0 limϵ0 0 q(ϵ0, ϵ1) 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 to compute the optimal gain of the necklace policy we introduce the following two lemmas.

**Lemma 4.1. Assume a discrete random walk on a chain of sites indexed by i, with probabilities ri**
_to step from i to i + 1 and li to step from i to i −_ 1. Starting in site i, the probability to reach site
_j + 1 (i ≤_ _j) before site i −_ 1 is

_li+1_ _−1_

_Pi_ _j =_ 1 + _[l][i]_ + _[l][i]_ + + _[l][i]_ _. . . [l][j]_ _._ (8)
_→_ _ri_ _ri_ _ri+1_ _· · ·_ _ri_ _rj_
 

_Proof. The proof is developed in Appendix D.1._


**Lemma 4.2. Assume a discrete random walk on a chain of n + 2 sites indexed by i = 0, 1, . . . n + 1**
_(with probabilities ri to step to the right and li to the left). If r0 = ϵR and ln+1 = ϵL, in the limit_
_ϵ →_ 0, the probability to be on site n + 1 is

_n_ _−1_

_li_

_p(n + 1) =_ 1 + _[L]_ _._ (9)

_R_ _i=1_ _ri_ !

Y

_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 in (4) in the limit of small reset**
_r_ 0. The necklace policy described in Definition 4.1 with parameters (ϵ0, ϵ1) has a probability q
_→_
_to play the worst arm satisfying q ≥_ _q[∗], with:_

_q[∗]_ = 1 + α[m][(1][−][n][(][m][))][][−][1] _with α = [1][ −]_ _[µ]_ (10)

1 + µ _[.]_



_The optimal necklace policy converges to q[∗]_ _when r_ _ϵ0_ _ϵ1_ 1.
_≪_ _≪_ _≪_

_Proof. The detailed proof is contained in Appendix D.3._

**Note** At leading order q[∗] = α[2][m] + o(α[2][m] ). This is because the number of distinct necklaces
_N_ (m) only differs from 2+(2[m] _−_ 2)/m at second order, and because we expect to find Gray orders
within those distinct necklaces whose length only differ from N (m) at second order.


-----

0.5

0.4

0.3

0.2

0.1

0.0

0.5

0.4

0.3

0.2

0.1

0.0

|Col1|RAM M = 8, r = 10−3|Col3|Memento m = 3, r = 10−3|Col5|Col6|Meff = 64, r = 10−5|Col8|Col9|
|---|---|---|---|---|---|---|---|---|
||A||C|||E|||
||||||||||
||||||||||
||||||||||
||||||||||
||||||||||
||||||||||
||RAM random RAM linear RAM columns RAM CCP||Memento random Memento cycles Memento necklace|||Memento random RAM random CCP necklace (r = 0)|||
||||||||||


|Col1|RAM M = 20, r = 10−3|Col3|Memento m = 4, r = 10−3|Col5|Col6|Meff = 256, r = 10−5|Col8|Col9|
|---|---|---|---|---|---|---|---|---|
||B||D|||F|||
||||||||||
||||||||||
||||||||||
||||||||||
||||||||||
||||||||||
||RAM random RAM linear RAM columns RAM CCP||Memento random Memento cycles Memento necklace|||Memento random RAM random CCP necklace (r = 0)|||
||||||||||


10[0] 10[3] 10[6]


Memento m = 4, r = 10[−][3]

D

Memento random
Memento cycles
Memento necklace

10[0] 10[3] 10[6]


_Meff = 256, r = 10[−][5]_

F

Memento random
RAM random
CCP
necklace (r = 0)

10[0] 10[3] 10[6]


Figure 4: Dynamics of the optimization algorithm for different initialization methods. Probability
to play the worse arm q vs. algorithm time t (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, the
_linear initialization where the jumps in memory states are 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 1 and the CCP initialization, very close to the column of
decrease).confidence policy (i.e. C-D q vs. t π for the Memento memory0 ≈ _πCCP + 10[−][4], a difference that explains why the red curves can m = 3 and m = 4. We compare the random_
initialization with the cycles initialization that repeats the oldest action, except if all the remembered
plays correspond to a maximally informative event (during training a path between the cycles has to
be learned) and the necklace where ϵ0 and ϵ1 has to be learned. E-F q vs. t 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 Meff 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
_r = 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 probability q(t) to play the worse arm after a training time t depends on the initialization of policy. For the
RAM memory, we find that random initialization (blue curves) leads to very poor results (panels A
and B of Figure 4). Results however improve when a linear structure for memory states is imposed
(orange curves) and when the arms played are segregated on the two sides of that linear structure


-----

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 4, 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 memories), we find that, for random initialization, the Memento architecture leads to actually better
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 Meff constant. This finding emphasizes the need to constrain memory architecture, so as to obtain smoother optimization
landscapes.

6 CONCLUSION

Policies

Memory scheme Memento (cf. 2.6) RAM (cf. 2.5)
Policy necklace (cf. 4.1) CCP (cf. 3.1)
Effective memory _Meff = 4[m]_ _Meff = 4M_
Performance (q[−][1] _−_ 1) _α[m][(1][−][n][(][m][))]_ _∼_ _α[−][2][m]_ _α[−][(2][M]_ _[−][1)]_

... as function of Meff _α[−√][M][eff]_ _α[−][M][eff]_ _[/][2]_

_m_ _∼_ _m(n(m)_ 2)/2 _∼_ _M_ 1

1 _kB_ 1/kB 1 _−_ 1 _kB_ 1/kB 1 _−_
... more generally for (kA > kB) 1−−kA 1/kA−−1 1−−kA 1/kA−−1
     

Table 1: Comparison of the performances of the necklace and CCP strategies in the limit r → 0.
As shown in the last line, the gain of these policies can be generalized to any distribution of the
Bernoulli probabilities kA and kB (but needs not be optimal then).

Our results are summarized in Table 1 that compares the necklace policy (cf. 4.1) and the column of
confidence policy (cf. 3.1). For each of these policies, we provide the optimal performance, reached
in 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 in Figure 3: the best numerical policies found for m = 3 and m = 4 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 & Lakshmanan (1978); 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 as those
involved in navigation (Theocharous et al. (2004); Toussaint et al. (2008)), would have practical
applications. Looking ahead, it would be interesting to 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 to be optimal. Despite the fact that our set-up is intrinsically digital, optimal policies approach 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. In neuroscience,
dominants models of decision making often present a single analogue variable being updated by
observations (Gold & Shadlen (2007); Rescorla & Wagner (1972)). It would be interesting to test
experimentally, in situations where the environment can change with a small probability r between
two distinct classes, if animals stick to two extreme believes, and leave them for exploration with
some rate ∼ _[√]r._


-----

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 B. Lakshmanan. Finite memory multiple hypothesis
testing: Close-to-optimal schemes for bernoulli problems. IEEE Transactions on Information
_Theory, 24(6):755–759, 1978._

Thomas M. Cover and Martin E. Hellman. The two-armed-bandit problem with time-invariant finite
memory. IEEE Transactions on Information Theory, 16(2):185–195, 1970. doi: 10.1109/TIT.
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.
_arXiv preprint arXiv:1507.06527, 2015._

Milos Hauskrecht. Value-function approximations for partially observable markov decision processes. 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–782, 1970. ISSN 0003-4851._

Tommi Jaakkola, Satinder P. 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 arXiv:1509.03044, 2015.

Michael L. Littman. An optimization-based categorization of reinforcement learning environments.
_From animals to animats, 2:262–270, 1993._

Nicolas Meuleau, Kee-Eung Kim, Leslie Pack Kaelbling, and Anthony R. Cassandra. Solving 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, Stockholm, Sweden, July 30 - August 1, 1999, pp. 417–426. Morgan Kaufmann,_
1999. [URL https://dslpitt.org/uai/displayArticleDetails.jsp?mmnu=](https://dslpitt.org/uai/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=194&proceeding_id=15)
[1&smnu=2&article_id=194&proceeding_id=15.](https://dslpitt.org/uai/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=194&proceeding_id=15)

Nicolas Meuleau, Leonid Peshkin, Kee-Eung Kim, and Leslie Pack Kaelbling. Learning finite-state
controllers for partially observable environments. arXiv preprint arXiv:1301.6721, 2013.

Junhyuk Oh, Valliappa Chockalingam, Honglak Lee, et al. Control of memory, active perception,
and action in minecraft. In International Conference on 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 Lerer. Automatic differentiation in
pytorch. 2017.

Leonid Peshkin, Nicolas Meuleau, and Leslie Kaelbling. Learning policies with external memory.
_arXiv preprint cs/0103003, 2001._


-----

George P´olya. Kombinatorische anzahlbestimmungen f¨ur gruppen, graphen und chemische
verbindungen. Acta mathematica, 68(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-Crofts, 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 J. Sondik. The optimal control of partially observable markov
processes over a finite horizon. Operations research, 21(5):1071–1088, 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 Leslie 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. McIlraith. The act of remembering: A study in partially observable
reinforcement learning. arXiv:2010.01753 [cs], 2020.

Marc 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):279–292, 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 IEEE International Conference
_on Robotics and Automation (ICRA), pp. 520–527, 2016. doi: 10.1109/ICRA.2016.7487174._


-----

# Appendices

A PROOF OF LEMMA 2.1

_Proof. The state transition matrix of the undiscounted POMDP is_

_T˜π(s[′]_ _s) = rp0(s[′]) + (1_ _r)Tπ(s[′]_ _s)._ (11)
_|_ _−_ _|_

The steady state p(s) has to be stable through _T[˜]π, thus satisfying p(s[′]) =_ _s_ _T[˜]π(s[′]|s)p(s). In the_

tensor form, it can be written ⃗p = r⃗p0 + (1 − _r)Tπp⃗. Applying recursively this formula n times we_
obtain:

_n−1_ [P]

_p⃗ = r_ (1 − _r)[t]Tπ[t]_ _p[⃗]0 + (1 −_ _r)[n]Tπ[n]p.[⃗]_ (12)

_t=0_

X


Translating it into an expectation value expression we obtain:


_n−1_

(1 _r)[t]f_ (st)

" _t=0_ _−_
X


Es∼p[f (s)] = r Est∼T tπ[p][0]


+ (1 − _r)[n]Es∼Tπ[n][p][[][f]_ [(][s][)]] (13)


for any function f and where Tπp is understood as a matrix-vector product (note that Tπp = p). By
_̸_
replacing f by R and by taking the limit n →∞, for r = 1 − _γ, we can identify (13) with (2), thus_
obtaining the Lemma 2.1.

B IMPLEMENTATION DETAILS

To compute the steady state we use the power method algorithm: Alg.1.

When we have multiple independent environments (by environment we mean subset of S that the
agent cannot escape with its actions), S is the disjoint union of these environments: S = S1 + S2 +
_. . . . If p0 factorize as follow p0(s) = P_ (Si)P (s|Si) for s ∈ _Si, 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 p0. It could mathematically be reformulated as special actions done on special initial
states to initialize the memory.

**Data: A transition matrix M**
**Result: The steady state**
**while the columns of M differ (with a 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, see the link in Section 1.

Here we compute the optimal value of ϵ (that maximize the gain) given r and µ.

First observe that the states (3B+, 1A-, ...) can be arranged along a line:

MA+ _. . ._ 2A+ 1A+ 1B+ 2B+ _. . ._ MB+
(14)
MA− _. . ._ 2A− 1A− 1B− 2B− _. . ._ MB−

where the probability transition only occurs between two consecutive states.


-----

If we merge the ± we have 2M states and we can compute their transition matrix without reset:


1 _ϵkB_ _kA_
_−_
_ϵkB_ 0 _kA_



_kB_ 0 ...

_Q =_ 

 _kB_ ... _kA_

 ... 0 _ϵkA_
 _kB_ 1 _ϵkA_
 _−_


where kA = (1 + µ)/2 and kB = (1 − _µ)/2_

Including the reset, the transition probability becomes


(15)


_Mij = (1 −_ _r)Qij + rJi_ (16)

where J is 1/2 in the two central states 1A and 1B.

The steady state pi is the solution of


((1 − _r)Qij −_ _δij)pj = −Ji_ (17)


_Mijpj = pi_


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) is
(1 _r)kBpi_ 1 _pi + (1_ _r)kApi+1 = 0_ (18)
_−_ _−_ _−_ _−_

The solutions are of the form pi = c1w+[i] [+][ c][2][w][i]
_−_ [with]


_w_ = [1][ ±]
_±_


1 − (1 − _r)[2](1 −_ _µ[2])_ (19)

(1 − _r)(1 + µ)_


To fix the coefficients c1, c2 in the two bulks we have 6 equations:

-  two on the left border (two first lines of (17))

-  two in the center, at the injection (two middle lines of (17))

-  two on the right border (two last lines of (17))

Solving these equations, we can compute the probability to play the wrong arm (B, assuming µ > 0).

_w+(1 + w+)(1 −_ _w−)w−[2][M]_ [(1 +][ w][+][(][ϵ][ −] [1))(][w][−] [+][ ϵ][ −] [1)]
+(w+ ↔ _w−)_

_q =_ +(w−w+)[M] (w−w+ − 1)((w− _−_ 1)(w+ − 1)(w− + w+)(ϵ − 1) + 2w−w+ϵ[2]) (20)

2(w− _−_ _w+)(w+[2][M]_ _[w][−][(1 +][ w][−][(][ϵ][ −]_ [1))(][w][+] [+][ ϵ][ −] [1)][ −] [(][w][+] _[↔]_ _[w][−][))]_

in this expression of q we expressed r, µ and kA, kB in function of w
_±_

Optimizing q with respect to ϵ leads to


(w 1)w[M] + [(][w][−][w][+] + [)][2]
_−_ _−_ _−_ [(][w][+] _[−]_ [1)][w][M] _[−]_ [1)(][w]−[M] _[w][+]_ _[−]_ _[w][−][w][M]_

(w− _−_ 1)(w+ −w1)([3][M]w−+w[(1 +]+)[1+2][ w][M][−]([)(1 +]w−w[ w]+ −[+][)] 1)[2](w+[M] _[−]_ _[w]−[M]_ [)]

_−_ _[w][2]_
_−(w+ ↔_ _w−)_
+w+[2][M] _[w][1+][M]_ (2w+ + w + w+w (7 + 2w+) + w[2]
_−_ _−−(w+ ↔−w−)_ _−[(][w][+]_ _[−]_ [1))]

(w−w+ − 1)  _w−[2]_ _[w]+[2][M]_ [(1 +]+(w[ w]+[−] ↔[(][w][+]w−[−])[1) +][ w][+][)] 

_−2w−[1+][M]_ _w+[1+][M]_ (1 + w−w+)
 


_ϵ = (w−w+)[−][M]_


(21)


-----

We can make the Taylor expansion of ϵ with respect to r


_α −_ _√α[3]1[M] −[−][1]α[M]+ α(1[M] −(2αµ[M] −−3) +µ − αα[2][M][M]µ(2)_ _µ + 3)_ _√r + O(r)_ (22)


_ϵ =_


with α = [1]1+[−]µ[µ]


For M large, it converge quickly toward

2r
_ϵ =_ (23)

1 _µ[2][ +][ O][(][r][)]_

r _−_


In the limit r → 0 we get


_α[2][M]_ _[−][1]_
_q =_ (24)

_α[2][M]_ _[−][1]_ + 1 [+][ O][(][√][r][)]


D RANDOM WALK ALONG A CHAIN

D.1 PROBABILITY TO TRAVERSE THE CHAIN

1 − (li + ri)

_li_ _ri_


_i −_ 1 _i_ _i + 1_

Figure 5: Markov chain

Consider a random walk on a chain of sites with probabilities ri to move from site i to i + 1 and li
to move from i to i 1 (Figure 5). First, we want to compute the probability Pi _j (with i_ _j) that,_
_−_ _→_ _≤_
starting at site i, the walker visits the site j + 1 before the site i 1. Note that Pi _j only depends_
onPi← {jl as the probability to reachk}k[j] =i [and][ {][r][k][}]k[j] =i[. Note also that according to this definition] i − 1 before j + 1 by starting in − j, then we have[ P][i][→][i][ =] _li+ri Pri→[. We also define]i←i =_ _li+liri_ [.]

Starting in i, after one time step the walker is either (i) in i 1 (with probability li) and the probability
_−_
to reach j +1 before reaching i _−_ 1 becomes null, (ii) still in i (with probability 1 _−_ (li + _ri)) and the_
probability to each j + 1 before i − 1 is still given by Pi→j, (iii) in i + 1 (with probability ri). Once
in i +1 there are two possibilities: either the walker never comes back to i and it reaches j +1 (with
probability Pi+1→j), or it does (with probability 1 − _Pi+1→j) and it again has the same probability_
_Pi_ _j to reach j + 1 before i_ 1. Thus we have:
_→_ _−_

_Pi_ _j = (1_ (li + ri))Pi _j + ri (Pi+1_ _j + (1_ _Pi+1_ _j)Pi_ _j) ._ (25)
_→_ _−_ _→_ _→_ _−_ _→_ _→_

The quantities that matter are pi _ri/(li + ri). If we isolate Pi_ _j to the l.h.s. we get_
_≡_ _→_

_Pi_ _j =_ _piPi+1→j_ (26)
_→_ 1 − _pi(1 −_ _Pi+1→j)_ _[.]_

Making the changes of variable Xi→j ≡ [1][−]Pi[P]→[i][→]j _[j]_ and xi ≡ [1][−]pi[p][i] (note that xi = li/ri) we obtain

_Xi_ _j = xi(1 + Xi+1_ _j)._ (27)
_→_ _→_

By repeating the formula we see that we get


_l=i_ _xl = xi + xixi+1 + xixi+1xi+2 + · · · + xi · · · xj_ (28)

Y


_Xi_ _j =_
_→_


_k=i_


from which we can get Pi _j by the inverse transformation_
_→_


_−1_
_._ (29)



_Pi_ _j =_ 1 + _[l][i]_ + _[l][i]_
_→_ _ri_ _ri_



_li+1_

+ + _[l][i]_ _[l][j]_
_ri+1_ _· · ·_ _ri_ _· · ·_ _rj_


-----

D.2 CHAIN WITH FINAL STATES

Let us consider the same chain as above with a finite length n such that sites are labelled from i = 1
to n. Now let us add a final state at each end of the chain (sites i = 0 and n + 1). We consider the
probabilities to leave the final states asymptotically small, of order ϵ. More precisely, the probability
to move from i = 0 to 1 is ϵR (we call it R as it is a probability to go to the Right, although it
concerns the most left site) and the probability to move from n + 1 to n is ϵL. These probability and
the probabilities p(0) and p(n + 1) to be on the site 0 and n + 1 are related by a balance of the flow
from 0 to n + 1:

_p(0)ϵRP1_ _n = p(n + 1)ϵLP1_ _n._ (30)
_→_ _←_

In the limit ϵ → 0, the probabilities to be in the extreme states tends to 1 and we thus have p(0) =
1 − _p(n + 1), yielding_


_−1_
_._ (31)



_p(n + 1) =_ 1 + _[L]_

_R_



This result can be simplified using the equality


_P1←n_
_P1→n_


_P1←n_ = 1 + _r[l][1]1_ [+][ · · ·][ +][ l]r[1]1 _[. . .][ l]r[n]n_
_P1→n_ 1 + _[r]ln[n]_ [+][ · · ·][ +][ r]ln[n] _[. . .][ r]l1[1]_


_li_

_,_ (32)
_ri_

(33)


_i=1_


to finally obtain the formula

D.3 CHAIN OF NECKLACES


_−1_
!


1 + _[L]_


_li_

_ri_


_p(n + 1) =_


_i=1_


To compute the gain of the necklace policy, the idea is to show that necklaces can be arranged on a
chain so that we can use (33) (see Figure 3).

For m prime, the number of non trivial necklaces is (2[m] _−_ 2)/m, the trivial necklaces being the two
final states (i.e., the words AAA..A and BBB..B). Using the conjecture of Degni & Drisko (2007),
there is a Gray order on these necklaces when m is prime. In other words, there is 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
_y(m) the length of the smallest necklace in that longest chain (arguably the smallest prime factor of_
_m)._

A necklace is characterized by the numbers a and b of letters A and B in the m-long word, with
_a + b = m. After at least one complete loop in the necklace (i.e. at least y(m) actions), the_
probabilities to leave that necklace (when we are at the exit states) are

_li = ϵ1kA[a]_ [(1][ −] _[k][B][)][b][,]_ (34)

_ri = ϵ1(1 −_ _kA)[a]kB[b]_ _[.]_ (35)


With the odds to do at least one loop increasing as ϵ1 goes to zero or y(m) goes to ∞.

In the two final states, and again after one loop, the probabilities to leave are ϵ0L = ϵ0(1 _kB)[m]_
_−_
and ϵ0R = ϵ0(1 _kA)[m]. We can now use the formula (33) (when ϵ0_ _ϵ1_ 1), in which the
_−_ _≪_ _≪_


-----

product simplifies as


_n_ _li_ _n(m)−2_ _kA[a][i]_ [(1][ −] _[k][B][)][b][i]_

= (36)

_i=1_ _ri_ _i=1_ (1 _kA)[a][i]_ _kB[b][i]_

Y Y _−_

= Qinni=1=1((mm))−−22(1(1/k/kAB − 1)1)[a][b][i][i] (37)

_−_

_i_ _[b][i]_

Q

= (1[(1]/k[/k]A[B][ −] 1)[1)]Pi _[a][i]_ (38)

1/kB − 1Pm(n(m)−2)/2 _n(m)−2_
= _−_ since (ai + bi) = m(n(m) 2) (39)

1/kA 1 _−_

 _−_  Xi=1

where ai and bi are the occurrences of 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 + α[m][(1][−][n][(][m][))][][−][1] _,_ with α = [1][ −] _[µ]_ (40)

1 + µ _[.]_



and p(0) can be obtained by changing µ into −µ or α into 1/α, 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. HB), the value p(n + 1) (resp. p(0)) corresponds to the probability q[∗]
to play the worst arm if the probabilities of the non-final necklaces are zero (which is asymptotically
true ifleast one loop in each necklace and ϵ0 ≪ _ϵ1). To reach q[∗], we also need ϵ0 has to be asymptotically larger than the reset ϵ1 to be asymptotically small in order to guarantee at r. In summary,_
we need r _ϵ0_ _ϵ1_ 1 to reach asymptotically q[∗], otherwise the probability q will be larger
than q[∗]. _≪_ _≪_ _≪_

D.4 COLUMN OF CONFIDENCE POLICY WITH NO RESET

When there is no reset r = 0 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
_−_

1/kA 1

 _−_


_M_ _−1_
(41)



_q[−][1]_ 1 = [1][ −] _[k][B]_
_−_ 1 _kA_

_−_


-----

