# How memory architecture affects learning in a simple POMDP: the two-hypothesis testing problem

arXiv: https://arxiv.org/abs/2106.08849 · HTML: https://mlsanity.com/paper/2106.08849/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 34 references that are in the map.
- First posted on arXiv 16 Jun 2021.

## Builds on (most cited first, 8 of 8)

- [Deep Recurrent Q-Learning for Partially Observable MDPs](https://mlsanity.com/paper/1507.06527/) (2015)
- [DESPOT: Online POMDP Planning with Regularization](https://mlsanity.com/paper/1609.03250/) (2016)
- [Control of Memory, Active Perception, and Action in Minecraft](https://mlsanity.com/paper/1605.09128/) (2016)
- [Solving POMDPs by Searching the Space of Finite Policies](https://mlsanity.com/paper/1301.6720/) (2013)
- [Learning Finite-State Controllers for Partially Observable Environments](https://mlsanity.com/paper/1301.6721/) (2013)
- [Recurrent Reinforcement Learning: A Hybrid Approach](https://mlsanity.com/paper/1509.03044/) (2015)
- [Memory Augmented Control Networks](https://mlsanity.com/paper/1709.05706/) (2017)
- [The act of remembering: a study in partially observable reinforcement learning](https://mlsanity.com/paper/2010.01753/) (2020)

## Abstract (arXiv)

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.