Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: In this paper, the authors propose a series of methods to tackle policy learning in POMDPs. 

At the core of the proposed method sits an augmented memory that the agent is allowed to write on and read from at the time of decision making. 

This allows the agent to store some of its past to be used for future decision making. 

The authors raise a few training, stability, and limitation issues in prior work. And argue that their proposed method improves over the prior works.

The idea of using augmented memory is exciting and fundamental and definitely worth expanding.

However, I found a few issues with the presentation and contribution of this paper that I would be happy to share. 

1) Second line of abstract:
"Learn- ing memoryless policies is efficient and optimal in fully observable environments." It is not clear what the authors mean here. Is the learning of memoryless policy efficient and optimal? If yes, it would great if the authors could parse it.

If they mean memoryless policies are optimal, then I recommend the authors to restate this statement since it is incorrect. 

2) The authors state "can solve problems that were unsolvable using LSTMs" since it is an impossibility statement, I would recommend either proving a reference for such a statement or provide proof.

3) "Notice that neither q-learning nor 5-step actor-critic were able to understand how to use the B1 memory to consistently solve the gravity domain." I guess the authors mean the agent using q-learning or 5-step actor-critic were not able to learn how to use ... .

4) I strongly recommend the authors to use more concrete notation. It seems that they study episodic POMDP or maybe a fixed horizon. They mentioned episodic but did not define it. Also, it is not clear what are state, action, and observation spaces. Are they finite? In the analysis I found in the appendix, it seems the authors approach finite ones. But it would be useful to mention it in the main body since there are high-dimensional exps in the paper. Also, q is not defined. I checked the referenced paper,  Jaakkola et al. 1995, there it was also not clear what is q. They first define it for time step zero. Then later use it for any time step. They seem to not define P_\pi(s|m). It would be great if the authors could define these quantities. The authors state that "Pπ (s|o) is the probability of being in state s given that the observation is o, when following policy π" well, at what time step? Please define these terms. 

5) I did not understand the point of a recall task example on page 5. 
As the authors know, there are examples of POMDPs that constant actions are optimal. I am not sure what would a significant conclusion one can draw from such examples.


----------------
General evaluation:
6) Almost all the theoretical statements are straightforward results of definitions and provided for justification. They are useful in understanding the paper. I appreciate the authors for including them. 

7) I again encourage the authors to make their notation a bit more concrete. If they study fixed horizon POMDPs, where the stages (time step in the episode) are encoded?

8) While I appreciate the augmented memory type policy, it seems the authors' proposed method is quite fragile. For example, for the OAk setting, if the agent needs to store k pairs of (o_t,a_{t-1}) to achieve a good solution, then the method breaks? 

9) Such fragileness mentioned in 8 seems not to be an issue in methods that learn latent states. How would the authors handle that?

10) Since the contribution is empirical, I would be happy if the authors provide a study against existing baselines, e.g., those referred to in the related works. 

11) Regarding memoryless policies in pomdps, I recommend the authors to take a look at Policy Gradient in Partially Observable Environments: Approximation and Convergence. They seem to have some convergence analysis that might be useful.



---------
Post rebuttal.
I would like to thank the authors for their clarifying reply. I will discuss with other reviewers and AC, and update my evaluation further. 



review_title: The notation and explanation needs some treatment. The contribution is empirical, comparison with stronger baseline seems missing. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: This work proposes a lightweight approach to control memory in POMDPs. It is an alternative to heavier overhead approaches such as recurrent networks or memory-augmented networks (Oh et al. 2016).

The main contribution is to resurrect the old idea of simple lightweight memories and address what made them fail in complex domains by developing novel memory systems. The novel type of memory developed is the $Ok$ memory, wherein the agent is given a choice whether to push the most recent frame into the memory buffer or not. The commonly used $Kk$ memories in contrast push the most recent state into memory by default. 

+ The paper develops the theory of memory augmented POMDPs from basic principles and formalizes the learning problem.
+ A simple idea is methodically and thoroughly explored through experimentation. 
+ The paper is mostly well written and easy to follow with helpful toy problems and useful illustrations.

An obvious flaw with limited capacity buffer memory systems that store original observations is that longer term dependencies are harder to capture. This work offers a simple fix by including the decision of whether to store an observation or not into the agent's action space. But the system remains limited by having to store a fixed amount of full observations, as compared to more complex memory systems that can chose *what* to write along with when to write (eg. Neural map by Parisotto and Salakhutdinov 2017). Therefore, while the theory and evaluation are extensive, the memory system itself is limited and inefficient for environments where certain features of the state may need to be extracted and tracked for a long duration (not just a few frames).  

review_title: A simple fix for buffer-style memory systems with thorough theory and evaluation

final_score: rating: 7: Good paper, accept
review_content: The paper extends the agent actions with an ability to write to an external memory. The paper does a nice survey of the previous approaches. The paper explains the difficulties with bootstrapping and policy improvement in POMDPs. The paper proposes simple memories for storing a buffer of k observations. The agent has the ability to push or not to push the current observation to the buffer. The whole content of the external memory is visible to the agent at each time step.

The paper is nicely written and clear. I enjoyed reading the survey of the related work and the explanation of the problems.
I welcome that the paper tries to use RL to control the external memory. This topic deserves more research.

Suggestions to increase the paper impact:
1) The survey of the existing literature can be made more valuable by mentioning RL methods suitable for function approximation. As explained in "Reinforcement Learning: An Introduction", Section 17.3 "Observations and State" by Sutton and Barto, partial observability is a special case of function approximation.
2) It would be nice to mention the limitations of the different memories. Maybe that would help you to design better memories.
For example, if the task requires to count to N, you would need a memory with log2(N) bits. You can also discuss the need to use long n-step returns, e.g., n=2048.
3) The proposed Ok, OAk memories are not better at all tasks than LSTM. Consider using these memories *together* with LSTM.
It would be nice to get the benefits of both approaches.
review_title: Acting to remember, revisited

final_score: rating: 7: Good paper, accept
review_content: This paper focuses on reinforcement learning in partially-observable environments, and revisits the approach that consists of extending the agent with an external memory. The main contribution of the paper is the proposal (and evaluation) of adding an action to the agent, that allows it to push its current observation (and previous action is some cases) in a k-sized queue. The observation of the agent is extended with the contents of the queue. The main argument of the authors is that learning "when to push" is easier for the agent than learning "what to push" (as done with Neural Turing Machines and memory-bit external memories), and being able not to push the current observation allows the agent to remember past observations for longer durations, as opposed to k-step observation windows approaches.

The ideas proposed in the paper are simple and elegant. It seems surprising that this idea has not yet been proposed, but the paper shows great effort from the authors to look for related work, and discuss it. It just seems that a discussion of the work of McCallum in the late 90's is absent from this paper. McCallum, in his PhD thesis (and several papers before that), presents an algorithm that allows the agent to learn what observations to keep in a memory, and for how long. The implementation is, contrary to this paper, based on discrete data structures (trees for instance) and is more complicated than adding a "push current observation" action:

McCallum, R. "Reinforcement learning with selective perception and hidden state." (1997).

Work on Reinforcement Learning Neural Turing Machines is also related to what this paper present, but considers cases where the agent is trained (with backpropagation) on "what" to push on a memory tape, instead of simply being able to write the current observation on the memory tape:

Zaremba, Wojciech, and Ilya Sutskever. "Reinforcement learning neural turing machines-revised." arXiv preprint arXiv:1505.00521 (2015).

Clarity: my main complain with this paper is that it takes a very long time for the reader to see what the main contribution of the paper will be. The abstract and introduction both say that the paper will present a method that works in POMDPs, but does not state the method (the Ok memory). I would strongly advise the authors to explicitly mention, very early in the paper, that they propose to extend the agent with an action that allows the current observation to be enqueued in a fixed-length queue. A second (more minor) remark is that an intuition of what the Ok memory is (in addition to Definition 4.4) would help the reader understand that the agent observes the contents of the memory, and has an extra action to push the current observation onto it (is it really the case, by the way?)

Originality: the paper seems original. It is quite interesting that so much related work proposed ideas around what this paper proposes, but never exactly the formalism proposed in this paper.

Significance: the formalism presented in this paper could be applicable to a variety of POMDPs for which a finite set of past (possibly-continuous) observations help with executing good actions. Even though the paper does not point at real-world tasks that fit this definition, I believe that many "not that Markovian" real-world tasks could be solved using small Ok memories. As such, the significance of the work presented in this paper could be quite high.

To summarize my review:

- pros: simple idea, good empirical performance, applicable to many POMDPs
- cons: many pages of the paper must be read before understanding what its main contribution will be, and a discussion of industrial or real-world tasks that fit the class of POMDPs solvable with Ok memories would have been nice.

I therefore recommend (borderline) acceptance, but strongly suggest that the authors state their contribution in the abstract and introduction.

Author response: the updated paper is much clearer, and its abstract and introduction allow to clearly see what will be the contributions of this paper. I thank the authors for having followed my advice about this point. With this problem addressed, I recommend accepting this paper.
review_title: Allowing a reinforcement learning agent to push its current observation into a k-sized queue

Meta-review: This paper presents a refreshening insight into the classical idea of using external memory for reinforcement learning agents that learn and act in partially observable environments. The authors investigate a number of different memory architectures (Ok, OAk, Kk) and provide an insightful discussion on why we want to restrict the structure of the memory. 

Reviewers generally appreciated the technical contribution of the paper, although not very convinced that this work will have a significant impact on future work. AC is also not sure about the conclusion drawn from the paper, where policies with external memory could have better sample complexity compared to rnn-based policies. BTTT is computationally expensive, but it shall give better direction of which state to jump to, compared to the authors approach where the gradients are stopped at every timestep. So there should be pros and cons about this approach, and AC suspects that the sample complexity improvement actually comes from the fact that authors are explicitly limiting what can be stored in the memory, e.g. O or OA. This advantage can be broken in some other domains. AC admits that this is only a speculation at this point, but the motivation to use the external memory framework proposed in the paper needs to be more carefully investigated.

Decision: Reject