Year: 2021

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, i.e. q ∼ α2m 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.

text: 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 2m, i.e. q ∼ α2m 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.

heading: 1 INTRODUCTION
text: 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 2m —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. science/r/two-hypothesis-BAB3, and uses a function defined here https:// anonymous.4open.science/r/gradientflow/gradientflow. The experiments where executed on CPUs for about 10 thousand CPU hours.

heading: 2 POMDPS AND THE TWO-HYPOTHESIS TESTING PROBLEM

heading: 2.1 GENERAL FORMULATION
text: 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 function1, Ω 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) = ∑ o,a∈Ω×A T (s′|s, a)π(a|o)O(o|s). (1)
Definition 2.4 (Expected sum of discounted rewards). The expected sum of future discounted rewards of a policy π is
Gπ = E s0 ∼ p0 s1 ∼ Tπ(·|s0) s2 ∼ Tπ(·|s1) . . .
[ ∞∑ t=0 γtR(st) ] . (2)
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 undiscounted 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π = 1rEs∼p[R(s)].

heading: 2.2 OPTIMIZATION ALGORITHM
text: To optimize a policy algorithmically, we apply gradient descent on the expected sum of discounted rewards. First, we parametrize a policy with parameters w ∈ R|A|×|Ω|, normalized to get a probability using the softmax function πw(a|o) = exp(wao)∑
b exp(wbo) . Then, we compute the transition matrix
T̃π , from which we obtain the steady state p using the power method (See Appendix B). Finally, we 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 dt w = d dw Gπ(w). (3)

heading: 2.3 TWO-HYPOTHESIS TESTING PROBLEM
text: 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) kA = 1−µ 2 kB = 1+µ 2 (hypothesis HB)
(4)
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 − 2qπ). In the following, we will use qπ as a measure of performance, trying to find a policy π that minimizes qπ (and thus maximizes Gπ).

heading: 2.4 TYPES OF MEMORY CONSIDERED
text: 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 + log2M bits. Definition 2.6 (Memento Memory2). 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.

heading: 3 GAIN AND EXPLORATION WITH A RANDOM ACCESS MEMORY
text: 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 that HA is true if the memory state i is visited. Choose the labels i such that λ1 ≥ λ2... ≥ λM . Then it can be shown that λi/λi+1 ≤ α−1 (Hellman & Cover (1970)). The linear policy saturates this bound 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.
HB . From the stationary distribution T ~p = ~p, one obtains q( ), which reaches its minimum value for:
= √ 2 √ α− α3M−1 + αM (2µ− 3) + α2M (2µ+ 3)√
1− αM (1− αM − µ− αMµ) √ r +O(r) (6)
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:
qCCP(M) = α2M−1
α2M−1 + 1 . (7)
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.

heading: 4 GAIN FOR MEMENTO MEMORY
text: 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(lnm/m) (Auer et al. (2002)). It turns out that
our agent can use his own actions to encode events over a time much longer than m, leading to q exponentially small in 2m 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 lengthm (in combinatorics, a necklace is an equivalent class of character strings under cyclic rotation, here the strings are words of lengthmmade of the letters A and B, hence binary). Whenm is prime, there are exactlyN(m) = 2 + (2m − 2)/m distinct necklaces. For any m, the number of necklaces can be derived from Pólya (1937)’s enumeration theorem and is equal to N(m) = 1m ∑ d|m ϕ(d)2
m/d, where ϕ is the Euler’s totient function.
(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 + (2m − 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
Pi→j =
( 1 +
li ri + li ri li+1 ri+1 + · · ·+ li ri . . . lj rj
)−1 . (8)
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
p(n+ 1) = ( 1 + L
R n∏ i=1 li ri
)−1 . (9)
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− µ 1 + µ . (10)
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+(2m−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.

heading: 5 POLICY OPTIMIZATION AND LOCAL MINIMA
text: 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.
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.

heading: A PROOF OF LEMMA 2.1
text: 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:
~p = r n−1∑ t=0 (1− r)tT tπ~p0 + (1− r)nTnπ ~p. (12)
Translating it into an expectation value expression we obtain:
Es∼p[f(s)] = rEst∼T tπp0 [ n−1∑ t=0 (1− r)tf(st) ] + (1− r)nEs∼Tnπ p[f(s)] (13)
for any function f and where Tπp is understood as a matrix-vector product (note that Tπp 6= 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

heading: C EXACT COMPUTATION FOR COLUMN OF CONFIDENCE POLICY
text: 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+ MA− . . . 2A− 1A− 1B− 2B− . . . MB− (14)
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:
Q =  1− kB kA kB 0 kA kB 0 . . .
kB . . . kA . . . 0 kA
kB 1− kA
 (15)
where kA = (1 + µ)/2 and kB = (1− µ)/2 Including the reset, the transition probability becomes
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∑ j Mijpj = pi ⇐⇒ ∑ j ((1− r)Qij − δij)pj = −Ji (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) is
(1− r)kBpi−1 − pi + (1− r)kApi+1 = 0 (18)
The solutions are of the form pi = c1wi+ + c2w i − with
w± = 1± √ 1− (1− r)2(1− µ2) (1− r)(1 + µ)
(19)
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).
q =
w+(1 + w+)(1− w−)w2M− (1 + w+( − 1))(w− + − 1) +(w+ ↔ w−)
+(w−w+) M (w−w+ − 1)((w− − 1)(w+ − 1)(w− + w+)( − 1) + 2w−w+ 2)
2(w− − w+)(w2M+ w−(1 + w−( − 1))(w+ + − 1)− (w+ ↔ w−)) (20)
in this expression of q we expressed r, µ and kA, kB in function of w±
Optimizing q with respect to leads to
= (w−w+) −M
(w− − 1)wM− (w+ − 1)wM+ (w−w+ − 1)(wM− w+ − w−wM+ )2
− √√√√√√√√ (w− − 1)(w+ − 1)(w−w+)1+2M (w−w+ − 1)2(wM+ − wM− ) w 3M − w 2 +(1 + w−)(1 + w+) −(w+ ↔ w−)
+w2M+ w 1+M − (2w+ + w− + w+w−(7 + 2w+) + w 2 −(w+ − 1))
−(w+ ↔ w−)  (w−w+ − 1)
 w2−w2M+ (1 + w−(w+ − 1) + w+)+(w+ ↔ w−) −2w1+M− w1+M+ (1 + w−w+)  (21)
We can make the Taylor expansion of with respect to r
= √ 2 √ α− α3M−1 + αM (2µ− 3) + α2M (2µ+ 3)√
1− αM (1− αM − µ− αMµ) √ r +O(r) (22)
with α = 1−µ1+µ
For M large, it converge quickly toward
=
√ 2r
1− µ2 +O(r) (23)
In the limit r → 0 we get
q = α2M−1
α2M−1 + 1 +O(
√ r) (24)

heading: D RANDOM WALK ALONG A CHAIN
text: D.1 PROBABILITY TO TRAVERSE THE 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 on {lk}jk=i and {rk} j k=i. Note also that according to this definition Pi→i = ri li+ri
. We also define Pi←j as the probability to reach i− 1 before j + 1 by starting in j, then we have Pi←i = lili+ri .
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
1− pi(1− Pi+1→j) . (26)
Making the changes of variable Xi→j ≡ 1−Pi→jPi→j and xi ≡ 1−pi pi (note that xi = li/ri) we obtain
Xi→j = xi(1 +Xi+1→j). (27)
By repeating the formula we see that we get
Xi→j = j∑ k=i k∏ l=i xl = xi + xixi+1 + xixi+1xi+2 + · · ·+ xi · · ·xj (28)
from which we can get Pi→j by the inverse transformation
Pi→j =
( 1 +
li ri + li ri li+1 ri+1 + · · ·+ li ri · · · lj rj
)−1 . (29)
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
p(n+ 1) = ( 1 + L
R P1←n P1→n
)−1 . (31)
This result can be simplified using the equality
P1←n P1→n
= 1 + l1r1 + · · ·+ l1 r1 . . . lnrn
1 + rnln + · · ·+ rn ln . . . r1l1
= n∏ i=1 li ri , (32)
to finally obtain the formula
p(n+ 1) = ( 1 + L
R n∏ i=1 li ri
)−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 a chain so that we can use (33) (see Figure 3).
For m prime, the number of non trivial necklaces is (2m− 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 = 1k a A(1− kB)b, (34)
ri = 1(1− kA)akbB . (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∏ i=1 li ri = n(m)−2∏ i=1 kaiA (1− kB)bi (1− kA)aikbiB (36)
= ∏n(m)−2 i=1 (1/kB − 1)bi∏n(m)−2 i=1 (1/kA − 1)ai
(37)
= (1/kB − 1)
∑ i bi
(1/kA − 1) ∑ i ai
(38)
= ( 1/kB − 1 1/kA − 1 )m(n(m)−2)/2 since n(m)−2∑ i=1 (ai + bi) = m(n(m)− 2) (39)
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− µ 1 + µ . (40)
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 if 0 1). To reach q∗, we also need 1 to be asymptotically small in order to guarantee at least one loop in each necklace and 0 has to be asymptotically larger than the reset 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)
q−1 − 1 = 1− kB 1− kA ( 1/kB − 1 1/kA − 1 )M−1 (41)

Review summaries:
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. 

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:  (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.   (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.  The 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.