summaries: This paper is studying the problem of learning to interpret manuals / textual information about the task, with the goal of faster learning and generalization in RL. Unlike recent prior work (Narasimhan et al 2018, Zhong et al 2020) where the entities in the environment are already partly grounded to text (e.g. by representing them as their textual description), the agent here needs to learn the mapping between entities and corresponding text. In order to study this problem, the authors use a new environment and dataset of natural language descriptions, as well as propose a self-attention model that matches entities to relevant sentences. The proposed model performed comparable to a partly grounded policy (as in Narasimhan et al 2018).

summaries: The paper considers the task of training an agent to act following a manual expressed in natural language. The manual describes the roles and the behaviors of the entities in the environment. Each entity can be the goal, the message or the enemy and it can also be either fleeing, chasing or not moving. The agent has to bring the message to the goal while avoiding the enemy. A model called EMMA is proposed to change entity representations based on the manual, thereby making the agent aware of the entities’ roles. It is shown that EMMA is more effective than simple baselines.

summaries: Natural language grounding is an interesting research direction and has attracted many researchers in recent years. Previous work mainly considered grounding the text to image objects. This paper considers collaboratively to learn “entity” representations and natural language explanations with a reinforcement learning framework. Specifically, a multi-modal attention network is proposed to model the interaction between the entity representation and the text descriptions. The entire framework is trained over multiple games in a multi-task manner. Experiments are conducted on a newly designed benchmark. The proposed RL framework achieves reasonable performance in domain games (training & test are from the same games) and also has a strong zero-shot generalization to unseen games and "entities" (thanks to the parameter sharing and multi-task learning). Besides, the newly released dataset may facilitate future research in natural language grounding.

abstractText: In this paper, we consider the problem of leveraging textual descriptions to improve generalization of control policies to new scenarios. Unlike prior work in this space, we do not assume access to any form of prior knowledge connecting text and state observations, and learn both symbol grounding and control policy simultaneously. This is challenging due to a lack of concrete supervision, and incorrect groundings can result in worse performance than policies that do not use the text at all. We develop a new model, EMMA (Entity Mapper with Multi-modal Attention) which uses a multi-modal entity-conditioned attention module that allows for selective focus over relevant sentences in the manual for each entity in the environment. EMMA is end-to-end differentiable and can learn a latent grounding of entities and dynamics from text to observations using environment rewards as the only source of supervision. To empirically test our model, we design a new framework of 1320 games and collect text manuals with free-form natural language via crowd-sourcing. We demonstrate that EMMA achieves successful zeroshot generalization to unseen games with new dynamics, obtaining significantly higher rewards compared to multiple baselines. The grounding acquired by EMMA is also robust to noisy descriptions and linguistic variation.1

authors:
Jacob Andreas
Dan Klein

title: Alignment-based compositional semantics for instruction following

venue: In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing,

authors:
Jacob Andreas
Dan Klein
Sergey Levine

title: Modular multitask reinforcement learning with policy sketches

authors:
Dzmitry Bahdanau
Felix Hill
Jan Leike
Edward Hughes
Pushmeet Kohli
Edward Grefenstette

title: Learning to follow language instructions with adversarial reward induction

authors:
Yoshua Bengio
Jérôme Louradour
Ronan Collobert
Jason Weston

title: Curriculum learning

venue: In Proceedings of the 26th annual international conference on machine learning,

authors:
Valts Blukis
Yannick Terme
Eyvind Niklasson
Ross A Knepper
Yoav Artzi

title: Learning to map natural language instructions to physical quadcopter control using simulated flight

authors:
SRK Branavan
David Silver
Regina Barzilay

title: Learning to win by reading manuals in a montecarlo framework

venue: Journal of Artificial Intelligence Research,

authors:
Peter F Brown
Stephen A Della Pietra
Vincent J Della Pietra
Robert L Mercer

title: The mathematics of statistical machine translation: Parameter estimation

venue: Computational linguistics,

authors:
Michael Buhrmester
Tracy Kwang
Samuel D Gosling

title: Amazon’s mechanical turk: A new source of inexpensive, yet high-quality data? 2016

authors:
David L Chen
Raymond J Mooney

title: Learning to interpret natural language navigation instructions from observations

authors:
Maxime Chevalier-Boisvert
Dzmitry Bahdanau
Salem Lahlou
Lucas Willems
Chitwan Saharia
Thien Huu Nguyen
Yoshua Bengio

title: BabyAI: First steps towards grounded language learning with a human in the loop

venue: In International Conference on Learning Representations,

authors:
John D Co-Reyes
Abhishek Gupta
Suvansh Sanjeev
Nick Altieri
Jacob Andreas
John DeNero
Pieter Abbeel
Sergey Levine

title: Guiding policies with language via meta-learning

venue: arXiv preprint arXiv:1811.07882,

authors:
Andrea F Daniele
Mohit Bansal
Matthew R Walter

title: Navigational instruction generation as inverse reinforcement learning with neural machine translation

venue: 12th ACM/IEEE International Conference on Human-Robot Interaction (HRI,

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova. Bert

title: Pre-training of deep bidirectional transformers for language understanding

venue: arXiv preprint arXiv:1810.04805,

authors:
Daniel Fried
Jacob Andreas
Dan Klein

title: Unified pragmatic models for generating and following instructions. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)

authors:
Dave Golland
Percy Liang
Dan Klein

title: A game-theoretic approach to generating spatial descriptions

venue: In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing,

authors:
Sachithra Hemachandra
Matthew R Walter
Stefanie Tellex
Seth Teller

title: Learning spatialsemantic representations from natural language descriptions and scene classifications

venue: In Robotics and Automation (ICRA),

authors:
Karl Moritz Hermann
Felix Hill
Simon Green
Fumin Wang
Ryan Faulkner
Hubert Soyer
David Szepesvari
Wojciech Marian Czarnecki
Max Jaderberg
Denis Teplyashin

title: Grounded language learning in a simulated 3d world

venue: arXiv preprint arXiv:1706.06551,

authors:
Felix Hill
Andrew Lampinen
Rosalia Schneider
Stephen Clark
Matthew Botvinick
James L McClelland
Adam Santoro

title: Environmental drivers of systematicity and generalization in a situated agent

authors:
Felix Hill
Sona Mokra
Nathaniel Wong
Tim Harley

title: Human instruction-following with deep reinforcement learning via transfer-learning from text

venue: arXiv preprint arXiv:2005.09382,

authors:
Felix Hill
Olivier Tieleman
Tamara von Glehn
Nathaniel Wong
Hamza Merzic
Stephen Clark

title: Grounded language learning fast and slow

venue: arXiv preprint arXiv:2009.01719,

authors:
Ronghang Hu
Daniel Fried
Anna Rohrbach
Dan Klein
Trevor Darrell
Kate Saenko

title: Are you looking? grounding to multiple modalities in vision-and-language navigation

venue: In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics,

authors:
Michael Janner
Karthik Narasimhan
Regina Barzilay

title: Representation learning for grounded spatial reasoning

venue: Transactions of the Association for Computational Linguistics,

authors:
Diederik Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Heinrich Küttler
Nantas Nardelli
Alexander H Miller
Roberta Raileanu
Marco Selvatici
Edward Grefenstette
Tim Rocktäschel

title: The nethack learning environment

venue: In Advances in Neural Information Processing Systems,

authors:
Jelena Luketina
Nantas Nardelli
Gregory Farquhar
Jakob Foerster
Jacob Andreas
Edward Grefenstette
Shimon Whiteson
Tim Rocktäschel

title: A survey of reinforcement learning informed by natural language

venue: International Joint Conferences on Artificial Intelligence,

authors:
Dipendra Misra
John Langford
Yoav Artzi

title: Mapping instructions and visual observations to actions with reinforcement learning

venue: arXiv preprint arXiv:1704.08795,

authors:
Karthik Narasimhan
Regina Barzilay
Tommi Jaakkola

title: Grounding language for transfer in deep reinforcement learning

authors:
Junhyuk Oh
Satinder Singh
Honglak Lee
Pushmeet Kohli

title: Zero-shot task generalization with multi-task deep reinforcement learning

venue: arXiv preprint arXiv:1706.05064,

authors:
Hilke Reckman
Jeff Orkin
Deb Roy

title: Learning meanings of words and constructions, grounded in a virtual game

venue: Semantic Approaches in Natural Language Processing, pp

title: A video game description language for model-based or interactive learning

venue: In Computational Intelligence in Games (CIG),

authors:
John Schulman
Filip Wolski
Prafulla Dhariwal
Alec Radford
Oleg Klimov

title: Proximal policy optimization algorithms

venue: arXiv preprint arXiv:1707.06347,

authors:
Stefanie Tellex
Nakul Gopalan
Hadas Kress-Gazit
Cynthia Matuszek

title: Robots that use language

venue: Annual Review of Control, Robotics, and Autonomous Systems,

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

authors:
Matthew R Walter
Sachithra Hemachandra
Bianca Homberg
Stefanie Tellex
Seth Teller

title: Learning semantic maps from natural language descriptions

venue: Robotics: Science and Systems,

authors:
Xin Wang
Qiuyuan Huang
Asli Celikyilmaz
Jianfeng Gao
Dinghan Shen
Yuan-Fang Wang
William Yang Wang
Lei Zhang

title: Reinforced cross-modal matching and self-supervised imitation learning for vision-language navigation

authors:
Thomas Wolf
Lysandre Debut
Victor Sanh
Julien Chaumond
Clement Delangue
Anthony Moi
Pierric Cistac
Tim Rault
R’emi Louf
Morgan Funtowicz
Jamie Brew

title: Huggingface’s transformers: State-of-the-art natural language processing

title: All experiments were conducted on a single Nvidia RTX2080 GPU

heading: 1 INTRODUCTION

text:
Interactive game environments are useful for developing agents that learn grounded representations of language for autonomous decision making (Golland et al., 2010; Andreas & Klein, 2015; Bahdanau et al., 2018). The key objective in these learning setups is for the agent to utilize feedback from the environment to acquire linguistic representations (e.g. word vectors) that are optimized for the task. Figure 1 provides an example of such a setting, where the meaning of the word fleeing in the context is to “move away”, which is captured by the movements of that particular entity (wizard).
Learning a useful grounding of concepts can also help agents navigate new environments with previously unseen entities or dynamics. Recent research has explored this approach by grounding language descriptions to the transition and reward dynamics of an environment (Narasimhan et al., 2018; Zhong et al., 2020). While these methods demonstrate successful transfer to new settings, they require manual specification of some minimal grounding before the agent can learn (e.g. a ground-truth mapping between individual entities and their textual symbols).
In this paper, we propose a model to learn an effective grounding for entities and dynamics without requiring any prior mapping between text and state observations, using only scalar reward signals from the environment. To achieve this, there are two key inferences for an agent to make — (1) figure out which facts refer to which entities, and (2) understand what the facts mean to guide its decision making. To this end, we develop a new model called EMMA (Entity Mapper with Multimodal Attention), which simultaneously learns to select relevant sentences in the manual for each entity in the game as well as incorporate the corresponding text description into its control policy. This is done using a multi-modal attention mechanism which uses entity representations as queries to attend to specific tokens in the manual text. EMMA then generates a text-conditioned representation which is processed further by a deep neural network to generate a policy. We train the entire model in a multi-task fashion using reinforcement learning to maximize task returns.
1Code and data are available at https://www.dropbox.com/s/fnprjrfekbnxxru/code_data.zip?raw=1.
To empirically validate our approach, we develop a new multi-task framework containing 1320 games with varying dynamics, where the agent is provided with a text manual in English for each individual game. The manuals contain descriptions of the entities and world dynamics obtained through crowdsourced human writers. The games are designed such that two environments may be identical except for the reward function and terminal states. This approach makes it imperative for the agent to extract the correct information from the text in order to succeed on each game.
Our experiments demonstrate EMMA is able to outperform three types of baselines (languageagnostic, attention-ablated, and Bayesian attention) with a win rate almost 40% higher on training tasks. More importantly, the learned grounding helps our agent generalize well to previously unseen games without any further training (i.e. a zero-shot test), achieving up to a 79% win rate. Our model is also robust to noise and linguistic variation in the manuals. For instance, when provided an additional distractor description, EMMA still achieves a win-rate of 75% on unseen games.

heading: 2 RELATED WORK

text:
Grounding for instruction following Grounding natural language to policies has been explored in the context of instruction following in tasks like navigation (Chen & Mooney, 2011; Hermann et al., 2017; Fried et al., 2018; Wang et al., 2019; Daniele et al., 2017; Misra et al., 2017; Janner et al., 2018), games (Golland et al., 2010; Reckman et al., 2010; Andreas & Klein, 2015; Bahdanau et al., 2018; Küttler et al., 2020) or robotic control (Walter et al., 2013; Hemachandra et al., 2014; Blukis et al., 2019) (see Luketina et al. (2019) and Tellex et al. (2020) for more detailed surveys). Recent work has explored several methods for enabling generalization in instruction following, including environmental variations (Hill et al., 2020a), memory structures (Hill et al., 2020c) and pre-trained language models (Hill et al., 2020b). In a slightly different setting, Co-Reyes et al. (2018) use incremental guidance, where the text input is provided online, conditioned on the agent’s progress in the environment. Andreas et al. (2017) developed an agent that can use sub-goal specifications to deal with sparse rewards. Oh et al. (2017) use sub-task instructions and hierarchical reinforcement learning to complete tasks with long action sequences.
In all these works, the text conveys the goal to the agent (e.g. ‘move forward five steps’), thereby encouraging a direct connection between the instruction and the control policy. This tight coupling means that any grounding learned by the agent is likely to be tailored to the types of tasks seen in training, making generalization to a new distribution of dynamics or tasks challenging. In extreme cases, the agent may even function without acquiring an appropriate grounding between language and observations (Hu et al., 2019). In our setup, we assume that the text only provides high-level guidance without directly describing the correct actions for every game state.
Language grounding by reading manuals A different line of work has explored the use of language as an auxiliary source of knowledge through text manuals. These manuals provide useful descriptions of the entities in the world and their dynamics (e.g. how they move or interact with other entities) that are optional for the agent to make use of and do not directly reveal the actions it has to take. Branavan et al. (2012) developed an agent to play the game of Civilization more effectively by reading the game manual. They make use of dependency parses and predicate labeling to construct feature-based representations of the text, which are then used to construct the action-value function used by the agent. Our method does not require such feature construction.
Narasimhan et al. (2018) and Zhong et al. (2020) used text descriptions of game dynamics to learn policies that generalize to new environments, without requiring feature engineering. However, these works assume some form of initial grounding provided to the agent (e.g. a mapping between object IDs and their descriptions, or the use of entity names in text as state observations). In contrast, our model figures out even this fundamental mapping between entity IDs in observation space and their symbols in text entirely through interaction with the environment.

heading: 3 FRAMEWORK

text:
Our objective is to demonstrate grounding of environment dynamics and entities in a multi-task setup in order to drive generalization to unseen environments. Here and throughout, we refer to an entity as an object represented as a symbol in the observation that the agent may interact with.
Environment We model decision making in each environment as a Partially-Observable Markov Decision Process (POMDP) with the 8-tuple (S,A,O, P,R,E,Z,M). S and O are the set of all states and observations respectively where each o ∈ O contains entities from the set of entities E. At each step t, the agent takes some action at ∈ A. P (st+1|st, at) is the transition distribution over all possible next states st+1 conditioned on the current state st and action at. R(st, at, st+1) is a function that provides the agent with a reward rt ∈ R for action at and transition from st to st+1. Z is a set of text descriptions, with each z ∈ Z providing information about an entity e ∈ E. M is the map ze 7→ e which identifies the entity that each description describes. M , P , and R are not available to the agent. Note that there might not be a one-to-one mapping between Z and entities in the current state observation.
Reinforcement Learning (RL) The objective of the agent is to find a policy π : O → A to maximize its cumulative reward in an episode. If π is parameterized by θ, standard deep RL approaches optimize θ to maximize the expected reward of following πθ. In our setup, we want the agent to learn a policy πθ(a|o, Z) that conditions its behavior on the provided text. However, in contrast to previous work (Narasimhan et al., 2018; Zhong et al., 2020), M is not available to our agent and must be learned through interaction.

heading: 4 MODEL

text:
To learn a latent mapping between text symbols and entities, we develop a new model, EMMA (Entity Mapper with Multi-modal Attention), which employs a soft-attention mechanism over the text descriptions. At a high level, for each entity description, EMMA first generates key and value vectors from their respective token embeddings obtained using a pretrained language model. Each entity attends to the descriptors via a symbol embedding that acts as the attention query. Then, instead of representing each entity with its embedding, we use the resulting attention-scaled values as a proxy for the entity. This approach helps our model learn a control policy that focuses on entity roles (e.g. enemy, goal) while using the entities’ identity (e.g. queen, mage) to selectively read the text. We describe each component of EMMA below and in Figure 2.
Text encoder Our input consists of a h×w grid observation o ∈ O with a set of entity descriptions Z. We encode each description z ∈ Z using a BERT-base model whose parameters are fixed throughout training (Devlin et al., 2018; Wolf et al., 2019). For a description z, let t1, ..., tn be its token embeddings generated by our encoder. We obtain key and value vectors kz, vz:
kz = n∑ i=1 αiWkti + bk, α = softmax ( (uk · tj)nj=1 ) (1)
vz = n∑ i=1 βiWvti + bv, β = softmax ( (uv · tj)nj=1 ) (2)
The key and value vectors are simply linear combinations of Wkti + bk and Wvti + bv with weights α, β respectively, whereWk,Wv are matrices which transform each token to d dimensions and bk, bv are biases. The weights α, β are obtained by taking the softmax over the dot products (uk · tj)nj=1
and (uv · tj)nj=1 respectively. These weights imbue our model with the ability to focus on relevant tokens. All of Wk, bk, uk,Wv, bv, uv are learned parameters.
Entity representation generator To get a representation for each non-avatar (non-player) entity e, we embed its symbol into a query vector qe of dimension d to attend to the descriptions z ∈ Z with their respective key and value vectors kz, vz . We use scaled dot-product attention (Vaswani et al., 2017) and denote the resulting representation for the entity e as xe:
xe = m∑ i=1 γivzi γ = softmax ((qe · kzj√ d )m j=1 ) (3)
where m = |Z| is the number of descriptions in the manual. This mechanism allows EMMA to accomplish two forms of language grounding: the key and query select relevant descriptions for each object by matching entities to names (e.g. mage), and the value extracts information relevant to the entities’ behaviors in the world (e.g. enemy, chasing).
For each entity e in the observation, we place its representation xe into a tensor X ∈ Rh×w×d at the same coordinates as the entity position in the observation o to maintain full spatial information. The representation for the avatar (player entity) is simply a learned embedding of dimension d.
Action Module To provide temporal information, we concatenate the outputs of the representation generator from the three most recent states to obtain a tensor X ′ ∈ Rh×w×3d. To get a distribution over the next actions π(a|o, Z), we run a 2D convolution on X ′ over the h,w dimensions. The flattened feature maps are passed through a fully-connected feed-forward network terminating in a softmax over the possible actions.
y = Flatten ( Conv2D(X ′) ) π(a|o, Z) = softmax ( FFN(y) ) (4)
In contrast to previous approaches that use global observation features to read the manual (Zhong et al., 2020), we build a text-conditioned representation for each entity (xe). One advantage is that xe can directly replace the entity embeddings typically used to embed the state observation in most models. This means EMMA’s action module can easily be swapped with existing models, such as txt2pi (Zhong et al., 2020) while still being completely end-to-end differentiable. Further details about EMMA and its design can be found in Appendix D.

heading: 5 EXPERIMENTAL SETUP

heading: 5.1 TASK

text:
Motivation and Design We require a domain in which grounding the text descriptions Z to dynamics and learning the mapping M for all the entities in E is necessary to obtain a good reward. Moreover, there must be enough environments to induce the mapping M .
With these requirements in mind, we devise a new multi-task domain Messenger using the Py-VGDL framework (Schaul, 2013). In Messenger, each entity can take on one of three roles: a dangerous enemy, a secret message, and a crucial goal. The player’s objective is to bring the message to the goal while avoiding the enemy. If the player encounters the enemy at any point in the game, or the goal without first obtaining the message, it loses the game and obtains a reward of −1. Rewards of 0.5 and 1 are provided for obtaining and delivering the message to the goal respectively. Each of the enemy, message, and goal roles may be filled by one of twelve different entities, and each is assigned a stationary, chasing, or fleeing movement type to provide varying dynamics. Each set of entity-role assignments (henceforth referred to as a game) is initialized on a 10× 10 grid. The agent can navigate via up, down, left, right, and stay actions and interacts with another entity when both occupy the same cell. Some game examples are presented in Figure 1.
The same set of entities with the same movements may be assigned different roles. Thus, two environments may have identical observations but differ in the reward function R (which is not available to the agent) and the text manual Z (which is available). Thus, our agent must learn to extract information from Z to succeed consistently.
Grounding Entities via Interaction In previous work (Zhong et al., 2020), every combination of entities is possibly observed during training. Thus, for an entity e, its symbol in the observation (e.g. K) is the only one that always appears together with its text symbol (e.g. queen). This co-occurrence provides a strong inherent bias towards the correct grounding without needing to act in the environment. We denote these games in which each entity can appear with every other entity as multicombination (MC) games.
The MC assumption may not always be realistic in practice — some entities are very unlikely to appear together (e.g. airplane, thief, sword) while others may co-occur exclusively with each other (e.g. mage, orb, sword). We denote games in which the same three entities always appear together as single-combination (SC) games.
For SC games, any text symbol in the manual (e.g. mage, enemy, the, etc.) co-occurs the same number of times with all entities present, providing the agent no information about M . Thus, the agent must ground
these entities entirely via interaction. That is, the agent must align the behavior of the entities with its grounding of enemy, message, goal. For example, if the agent has the message, interacts with entity e and obtains a reward of 1, it must infer from the description “The mage is the goal” that e must be a mage (assuming it has grounded goal correctly).
We divide the entities in Messenger into human, nature and fantasy sub-worlds (Fig. 3) and exclude from training any games in which entities from different sub-world appear together. In particular, the nature and fantasy subworlds form SC games and the human subworld forms the MC games.
Text Descriptions Unlike previous work on language grounding in grid environments (Zhong et al., 2020; Chevalier-Boisvert et al., 2019), we do not use templated or rule-generated text. We collected 3,881 unique free-form entity descriptions in English via Amazon Mechanical Turk (Buhrmester et al., 2016) by asking workers to paraphrase prompt sentences.
To increase the diversity of responses, the prompts were themselves produced from 82 crowdsourced templates When constructing the prompts, we intentionally inject multiple synonyms for each entity. Workers often further paraphrased these synonyms, resulting in multiple ways to describe the same en-
tity (e.g. airplane, jet, flying machine, aircraft, airliner etc.). Learning to map these different text symbols to the same entity is another unique challenge in Messenger.
Each training manual consists of a set of three descriptions, one for each enemy, message, and goal entities. In total there are over 1.3× 109 possible manuals each with an average length of 30 words. The total vocabulary size of the free-form descriptions is 1,016. Besides lower-casing the worker responses, we do not do any preprocessing. Example descriptions can be found in Table 1. Further details regarding data collection can be found in appendix A.
Train-Evaluation Split Each entity is trained on two out of three possible roles, with the third role reserved for validation and testing. This forces models to make compositional entity-role generalizations for every entity to succeed on the evaluation games. In total we have 44 training, 32 validation, and 32 test games. We train on 2,557 of the text descriptions and reserve 652 each for validation and testing respectively.
Comparison with Previous Environments The primary focus of our work is on robust grounding of entities with rich language, a variety of entity synonyms, in an interactive setting without any priors or co-occurrence biases to help induce this grounding. To this end, Messenger features numerous challenges not found in prior work.
In Narasimhan et al. (2018), an oracle is used to concatenate the text representation to its corresponding entity representation. Access to such an oracle is a strong assumption in the wild and eliminates the need to ground the entities altogether.
In RTFM (Zhong et al., 2020), the observation is a grid of text which shares a set of symbols with the manual and both manual and observations are embedded into the same space. A key challenge unique to Messenger is learning to map between the observation and manual when they are embedded into different spaces. Furthermore, in RTFM all combinations of entities appear during training, which as we explained earlier, provides an additional signal that may simplify the grounding problem.
RTFM uses a small number rule-based templates to construct each manual, and each entity is referred to in a single way (e.g. goblin is always goblin). In contrast, Messenger features thousands of completely free-form descriptions and each entity may be referenced in multiple ways. For a more detailed comparison of RTFM and Messenger, including why we do not simply extend RTFM can be found in Appendix B.1.

heading: 5.2 BASELINES

text:
1) Mean-Bag of Sentences (Mean-BOS) This is a variant of EMMA (our model) with the attention mechanism ablated. We average the value vectors obtained from equation 2 for each descriptor to obtain v̄ which is used by the action module.
v̄ = 1 |Z| ∑ z∈Z vz y = Flatten ( Conv2D(Emb(o)) ) π(a|o, Z) = softmax ( FFN([y; v̄]) ) (5)
2) Game ID-Conditioned (G-ID) To assess the importance of language in our setup, we test a model with no language understanding on Messenger. We provide an auxillary vector I of integer IDs that reveals the mapping between entity symbols and roles (Fig. 4). These integers are embedded and concatenated to form the vector vI which is used by the action module to generate a distribution over the next actions:
y = Flatten ( Conv2D(Emb(o)) ) π(a|o, Z) = softmax ( FFN([y; vI ])
) (6)
3) Bayesian Attention Module (BAM) This baseline uses a hard-attention mechanism with a naive Bayes classifier trained to learn M . This approach is similar to a word alignment model used in machine translation approaches such as the IBM Model 1 (Brown et al., 1993). Specifically, for some set of observed entities E′ ⊆ E in the current environment:
BAM(z, E′) = arg max e∈E′ P (e|z) P (z|e) = ∏ t∈z P (t|e) P (t|e) = C(t, e)∑ t′ C(t ′, e) (7)
where t ∈ z are tokens in z, t′ is any token in the manual vocabulary and C refers to co-occurence counts. We use Bayes’ rule to flip the conditional. We let xe = vz from equation 2 for the z that maps to e. If two descriptions map to the same entity, we take the one with higher P (e|z), and if an entity receives no assignment we represent it with a learned default embedding Emb(e). We pretrain BAM on 1.5× 106 episodes.
4) Oracle-Map (O-Map) To get a sense of the upper-bound on EMMA’s performance, we consider a model that has access to the descriptor to entity mapM , similar to Narasimhan et al. (2018). Thus, it is identical to EMMA except that the representation for each entity xe is obtained as in equation 8.
xe = ∑ z∈Z 1[M(z) = e]vz (8)

heading: 5.3 TRAINING AND EVALUATION

text:
Curriculum Learning the entity groundings directly on Messenger is too difficult for the models we consider. Our initial experiments revealed that EMMA could not learn an entity grounding efficiently in this setting (Figure 5 (middle)). Thus, we introduce a two-stage curriculum to train our models (Bengio et al., 2009). In stage 1 (S1), all entities begin two steps from the agent and are immovable. The agent either begins with or without the message and must interact with the correct entity. It is provided a reward of 1 if it does so, and −1 otherwise. Models are first pretrained on S1, and all model parameters are transferred to stage 2 (S2), where entities are mobile and the agent always begins without the message. In each training game there is one chasing, one fleeing and one immovable entity. On both S1 and S2 we train our models in a multi-task fashion by sampling a random game and appropriate manual at the start of each episode.
All models are end-to-end differentiable and we train them using proximal policy optimization (PPO) (Schulman et al., 2017) and the Adam optimizer (Kingma & Ba, 2014) with a constant learning rate of 5× 10−5. Additional details can be found in Appendix C.
Evaluation On S1 test games, the entities start in the same locations as the training games and are also immovable. Thus, a model can apply the same policy used during training provided it can infer the (unseen) entity-role assignments, effectively testing the state estimation capabilities of models.
On S2 test games, we introduce new combinations of object movements to test adaptation to new dynamics. Specifically, compared to training there are two chasing entities during testing instead of one. We also consider a simpler state estimation test (S2-SE) where entity movements are identical to those seen during training. Environment details can be found in Appendix B.
6 RESULTS
6.1 MULTI-TASK PERFORMANCE
Figures 5 (left and middle) show rewards for both train and validation games as a function of training steps. The advantage of textual understanding is clear; on both S1 and S2, EMMA and the O-Map baseline converge to good policies much faster than the other
baselines. However, EMMA trained directly on S2 with pretraining on S1 (EMMA-(no curriculum), Fig. 5) indicate that fitting directly onto S2 remains a challenge.
Table 2 details win rates on the training games, with a breakdown over single (SC) and multi combination (MC) games. We observe that the naive Bayes classifier can assign over 99% of training descriptors correctly on MC games. However, on SC games that require interactive entity grounding, win rates are up to 60% lower. Our model (EMMA) can consistently win on both multi and single combination games, demonstrating EMMA’s ability to ground entities using interaction and reward signals alone, without co-occurrences statistics between entity and text symbols to guide its grounding.
6.2 GENERALIZATION
New Entities To assess EMMA’s ability at picking up novel game mechanics which are not specified in the provided text, we introduce two new stationary collectibles into Messenger — a trap and gold which provide
additional rewards of −1 and 1 respectively. We finetune EMMA on the 32 validation games with these new entities. The model learns to collect the gold and avoid the trap while accomplishing the original objectives in Messenger (Figure 5 (right)). Compared to training from scratch, EMMA pretrained on the original Messenger games is able to achieve a much higher reward in this modified setting in the same amount of steps, exceeding the previous maximum reward of 1.5 in 1×106 steps.
Test games Results on test games are presented in Table 3. Both the G-ID and Mean-BOS baselines fail to generalize in all cases. The G-ID baseline has complete access to distinguishing information between games that is necessary to succeed. However it overfits to the entity-role assignments it has seen during training, resulting in poor test performance. BAM demonstrates some ability to generalize to test games, but performance on games with single-combination entities are considerably lower, bringing the average down.
In contrast, EMMA can win 85% and 79% of test games on S1 and S2 respectively, almost matching the performance of the O-Map model. It also performs the best on the S2-SE test games. By extracting information from the relevant descriptor for each entity, EMMA is able to drastically simplify each task — it simply needs to learn a policy for how to interact with enemy, messenger and goal archetypes instead of memorizing a policy for each entity. This facilitates knowledge sharing between games, and generalization to unseen games.

heading: 6.3 ROBUSTNESS

text:
Test-Time We first assess the robustness of trained BAM and EMMA models against text manual variations on S2 test games in table 4. We test each model’s ability to: (1) handle an extra descriptor for an entity not found in the game (Append), (2) reason about the role of objects without a descriptor by deleting a sentence from the input at random (Delete) and (3) generalize to unseen synonyms (Synonyms). For the last case, we use (unseen) templated descriptions filled in with entity synonyms not seen during training.
Both models can retain their performance when presented with an extraneous description, and suffer considerably when a description is deleted. A key difference, however, is in our model’s ability to generalize to unseen entity synonyms. EMMA wins almost 72% of games compared to 11% by the BAM model in this setting.
Train-Time We test the ability to learn entity groundings with added neutral entities and negated descriptions (Table 5).
Neutral entities. At the start of each episode, we randomly select one of five neutral entities and insert it into the observation. The neutral entities are not described by the text, do not interact with the agent and provide no reward signal. The neutral entities are distinct from the objects in figure 3.
Negation. On each training episode with probability 0.25 we select one description, negate it, and change the role. (e.g. the mage is an enemy becomes the mage is not the message).
This case forces the model to consider the roles of the other two entities to deduce the role of the entity with the negated description. While EMMA can ground entities and performs well with neutral entities, it sometimes fails to ground the entities correctly with negated descriptions, affecting its performance on test games.
6.4 ANALYSIS OF GROUNDING
We visualize the attention weights for EMMA in Figure 6. Our model is always trained on a set of three descriptors, but to assess the overall latent mapping learned by our model, we evaluate the attention weights over 12 descriptions, one for every entity. EMMA is able to place most weight for entity e onto its descriptor ze. In particular, EMMA learns a grounding for dog, bird, fish, mage, sword and orb — entities for which co-occurrence statistics provide no meaningful alignment information, demonstrating that our model can learn groundings for these entities via interaction alone. This also hints that the acquired grounding can enable EMMA to comfortably scale up to environments containing larger sets of entities.

heading: 7 CONCLUSION

text:
In this paper, we develop a new model, EMMA (Entity Mapper with Multi-modal Attention) to leverage textual descriptions for generalization of control policies to new environments. Unlike prior work, we do not assume access to any form of prior knowledge connecting text and state observations, and learn both symbol grounding and control policy simultaneously. EMMA employs a multi-modal entity-conditioned attention module and learns a latent grounding of entities and dynamics using only environment rewards. Our empirical results on a newly developed multi-task game framework with crowdsourced text manuals demonstrate that EMMA shows strong generalization performance and robust grounding of entities. We hope that these results can lead to further research in enabling generalization for RL using natural language.
Applications and Future Work Studying entity grounding in interactive settings (with humans or other agents) will be important for agents that act in the world and automatically learn new concepts. While EMMA generalizes well to unseen games, its performance when additional reasoning is required (negation, deleted descriptions) is lower and warrants further study. Furthermore, training EMMA directly on Messenger without a curriculum results in very poor performance. This demonstrates that learning stable entity groundings on Messenger remains a difficult problem with long trajectories and sparse rewards (training directly on S2) and when additional reasoning is required (negation). We leave this to future work.

heading: A TEXT MANUAL

text:
To collect the text manual, we first crowdsource 82 templates (with 2,214 possible descriptions after filling in the blanks). Each Amazon Mechanical Turk worker is asked to paraphrase a prompt sentence while preserving words in boldface (which become the blanks in our templates). We have three blanks per template, one each for the entity, role and an adjective. For each role (enemy, message, goal) we have three role words and three adjectives that are synonymous (Table 6). Each entity is also described in three synonymous ways. Thus, every entity-role assignment can be described in 27 different ways on the same template. Raw templates are filtered for duplicates, converted to lowercase, and corrected for typos to prevent confusion on downstream collection tasks.
To collect the free form text for a specific entity-role assignment, we first sample a random template and fill each blank with one of the three possible synonyms. The filled template becomes the prompt that is shown to the worker. Aside from lower-casing the free-form descriptions, we do no further pre-processing.
On all tasks (template and free-form) we provide an example prompt (which is distinct from the one provided) and examples to provide additional task clarity. For each prompt, we obtain two distinct paraphrased sentences to promote response diversity. To ensure fluency in all responses, we limited workers to those located in the United States with at least 10,000 completed HITs and an acceptance rate of ≥ 99%. On all data collection tasks, we limit a single worker to a maximum of 36 responses to ensure worker diversity. In total, 297 workers participated in the data collection process.

heading: B ENVIRONMENT DETAILS

text:
Details about Messenger can be found in table 7. On stage 1 (S1), the three entities start randomly in three out of four possible locations, two cells away from the avatar. The agent always begins in the center of the grid. It starts without the message with probability 0.8 and begin with the message otherwise. When the avatar obtains the message, we capture this information by changing the avatar symbol in the observation. On S1, we limit each episode to four steps and provide a reward of −1 if the agent does not complete the objective within this limit.
On stage 2 (S2), the avatar and entities are shuffled between four possible starting locations at the start of each episode. On S2, the mobile entities (fleeing, chasing) move at half the speed of the agent. On S2, we limit each episode to 64 steps and like in S1, we provide a reward of −1 if the agent does not complete the objective within this limit.
Since there are only 4 single-combination (SC) training games and 40 multi-combination (MC) training games, we sample the games non-uniformly at the start of each episode to ensure that there is enough interaction with SC entities to induce an entity grounding. On both S1 and S2, we sample an SC game with probability 0.25 and an MC game otherwise. Not all descriptions have movement type information (e.g. “chasing”). We also collect unknown type descriptions with no movement type information. During training, each description is independently an unknown type description with probability 0.15
Negation We procedurally generate the negated text by negating existential words (e.g. “is an enemy” becomes “is not an enemy”). We manually negate those descriptions not captured by the rules. During both training and evaluation, we provide a complete text manual without any negated description with 0.75 probability, and randomly select a description in the manual to negate otherwise. When we negate an entity description ze to z′e, we also change the role (“...is an enemy” becomes “...is not a goal”, for example). Thus the information present in the manual has not changed, but the agent must look at the remaining two descriptions to deduce the role of e with description z′e.
Transfer Learning We test transfer by introducing two new entities – a trap and a gold which provide rewards of −1 and 1 respectively. Both collectables are randomly shuffled between two possible starting locations at the start of each episode and do not move. We train the models in this new setting in a multi-task fashion on the 32 validation games. After the agent encounters either the trap or gold, the collected item disappears. Neither item terminates the episode and the agent can still win or lose the current episode regardless of whether it has picked up the gold or trap.
B.1 COMPARISON WITH RTFM
The main novelty of our work (both the Messenger environment and our model) is in specifically tackling the issue of entity grounding without any prior knowledge. To do this, Messenger in contrast to RTFM (1) does not have any signal connecting entities to text symbols, (2) features much richer language, and (3) requires interaction in the environment to ground entities to text. We describe these in more detail:
1. RTFM’s observation space consists of a grid of text which shares a set of symbols with the text manual. Thus, both the text in the manual and the observation are embedded into the same space (e.g. using the same word vectors), essentially providing models with the entity grounding upfront. In contrast, our environment has a separate set of symbols for the entities with no relation to the text in our manual. Thus, the entities and text are embedded into different spaces, and learning to map between these two spaces is the key challenge in our environment that has not been explored before.
2. RTFM features only 32 total rule-based templates for the text, and each entity can only be referred to in a single way (goblin is always goblin). In contrast, we crowdsourced thousands of completely free-form descriptions in two rounds using Amazon Mechanical
Turk. After obtaining the seed templates from the first round, we intentionally inject multiple synonyms for each entity to construct each prompt for the second round. Workers often further paraphrased these synonyms, resulting in 5, 6 or often more ways to describe the same entity (e.g. airplane, jet, flying machine, aircraft, airliner etc.). The need to map these different text symbols to the same entity further complicates the entity grounding problem in our case and more closely mirrors the challenges of grounding entities in the real world. We believe Messenger provides a much closer approximation to “natural” language compared to RTFM.
3. RTFM features all possible combinations of entities during training, which as we explained in Sec. 5.1 provides an additional signal that may simplify the grounding problem.
4. Furthermore, each entity in RTFM only moves in a single way, whereas in Messenger, each entity may have different dynamics such as fleeing, chasing, and immovable entities (and this is also described in the text). This also allows us to test our model’s ability to generalize to unseen dynamics with unseen entity movement combinations, whereas in RTFM the evaluation on unseen games is essentially state-estimation.
Messenger is quite similar to RTFM and shares several aspects (e.g. grid-world with different entities and goals). That said, there are numerous reasons why we were not able to adapt the original RTFM environment to meet our requirements. We enumerate them here:
1. The dynamics in RTFM make entity grounding (the primary focus of our work) difficult. Messenger requires much simpler reasoning than RTFM, and it is already too difficult to ground entities directly in Messenger without a curriculum. RTFM sidesteps the issue by providing this grounding beforehand.
2. Obtaining enough crowdsourced descriptions is hard with RTFM because of the more complicated dynamics. In RTFM, there are monsters, weapons, elements, modifiers, teams, variable goals and different weaknesses between entity types that need to be specified. Collecting enough descriptions that are entirely human written would be challenging. (RTFM sidesteps this issue by using templates to generate their text manual). In contrast, there are only entities, 3 roles, and a fixed goal in Messenger, making the text-collection task much more tractable.
3. The entities in our Messenger environment are carefully chosen to make entity grounding harder. In RTFM, each entity is referred to in a single way, and it is not clear how to refer to them in multiple ways (e.g. there are not too many other ways to say goblin). In contrast, we specifically chose a set of entities that allowed for multiple ways of description, and actively encouraged this during data collection.
4. The combination of entities that appear during training in Messenger is carefully designed. This is so that we can introduce single-combination games and the associated grounding challenges that come with it.
5. We have different movement types for each entity. These different movements are referred to in our text manual and significantly increase the richness and variety of descriptions we collected, and also allow us to test generalization to unseen movement combinations. In RTFM, the entity movements are the same and fixed for all entities.
6. Each entity’s attribute is referenced in the observation in RTFM, e.g. the grid has entries such as fire goblin. We could add to the cell an extra symbol for fire, but this further obfuscates the entity grounding problem we are focusing on, because we would also need to obtain a grounding for all the attributes such as fire.
C IMPLEMENTATION DETAILS
For all experiments we use d = 256. When multiple entities E′ overlap in the observation, we fill the overlapping cell with the average of the entity representations 1|E′| ∑ e∈E′ xe. The convolutional layer consists of 2 × 2 kernels with stride 1 and 64 feature maps. The FFN in the action module is fully-connected with 3 layers and width of 128. To give the Mean-BOS and G-ID baselines the ability to handle the additional conditioning information, we introduce an additional layer of width
512 at the front of the FFN for those baselines only. Between each layer, we use leaky ReLU as the activation function. All models were trained for a maximum of 3×106 episodes on S1 and 36 hours on S2. All experiments were conducted on a single Nvidia RTX2080 GPU.

heading: D MODEL DESIGN

text:
The weights uk and uv were introduced to make sure that the token embeddings for filler words such as the, and, or do not drown out the words relevant to the task when we take the average in equations 1 and 2. Qualitatively, we observe that uk learns to focus on tokens informative for identifying the entity (e.g. mage, sword) while uv learns to focus on tokens that help identify the entities’ roles (e.g. enemy, message).
We also found that using a pretrained language model was critical for success due to the large number of ways to refer to a single entity (e.g. airplane, jet, flying machine, aircraft, airliner etc.).
D.1 MODEL VARIATIONS
We consider a variation to EMMA. Instead of obtaining token weights α, β in equations 1 and 2 by taking a softmax over the token-embedding and vector products uk · t and uv · t, we consider independently scaling each token using a sigmoid function. Specifically, we will obtain key and value vectors kz and vz using:
kz = n∑ i=1 σ(uk · ti)∑n i=1 σ(uk · ti) Wkti + bk (9)
vz = n∑ i=1 σ(uv · ti)∑n i=1 σ(uv · ti) Wvti + bv (10)
where σ is the sigmoid function, and all other details are identical to EMMA. We call this model EMMA-σ. We notice that both EMMA and EMMA-σ are able to obtain good training and validation performance, whith EMMA-σ obtaining higher rewards on S2. However, on S1, EMMA is able to obtain a higher validation reward faster (Fig. 7). Moreover, EMMA can learn robust groundings even with neutral entities, while EMMA-σ often overfits to a spurious grounding with neutral entities (Fig. 8). Although the independent scaling in EMMA-σ allows the model to consider more tokens simultaneously, the softmax selection of EMMA facilitates more focused selection of relevant tokens, and this may help prevent overfitting.


summaries: This paper presents AVEC, a new critic loss for model-free actor-critic Reinforcement Learning algorithms. The AVEC loss can be used with any actor-critic algorithm, with PPO, TRPO and SAC being evaluated in the paper. The loss builds on the mean-squared-error, and adds a term that minimizes $E_s [f_{\\phi}(s) - \\hat{V}^{\\pi_{\\theta_k}}(s) ]$. The addition of that extra term is motivated by recent research on the stability of actor-critic algorithms, and the benefits obtained by the AVEC loss are empirically demonstrated in numerous environments, with AVEC+PPO, AVEC+SAC and AVEC+TRPO.

summaries: The paper explores an alternative loss function for fitting critic in Reinforcement Learning. Instead of using the standard mean squared loss between critic predictions and value estimates, the authors propose to use a loss function that also incorporates a variance term. The authors dub the approach AVEC. The authors combine their approach with popular RL algorithms such as SAC and PPO and evaluated on the standard benchmarks for continuous control.

summaries: The paper proposes a simple and elegant idea for changing the value function objectives in deep RL and demonstrates reasonable empirical evidence of it's potential usefulness.  The authors also provide a clearly articulated intuitive motivation and provide experiments to support the proposal.  The idea complements several other algorithms and is therefore quite widely applicable (and easy to try). The analysis of the experiments is also quite interesting and clearly presented.

abstractText: Policy gradient algorithms have proven to be successful in diverse decision making and control tasks. However, these methods suffer from high sample complexity and instability issues. In this paper, we address these challenges by providing a different approach for training the critic in the actor-critic framework. Our work builds on recent studies indicating that traditional actor-critic algorithms do not succeed in fitting the true value function, calling for the need to identify a better objective for the critic. In our method, the critic uses a new state-value (resp. state-actionvalue) function approximation that learns the value of the states (resp. state-action pairs) relative to their mean value rather than the absolute value as in conventional actor-critic. We prove the theoretical consistency of the new gradient estimator and observe dramatic empirical improvement across a variety of continuous control tasks and algorithms. Furthermore, we validate our method in tasks with sparse rewards, where we provide experimental evidence and theoretical insights.

authors:
Marc Bellemare
Sriram Srinivasan
Georg Ostrovski
Tom Schaul
David Saxton
Remi Munos

title: Unifying count-based exploration and intrinsic motivation

authors:
Erwin Coumans
Yunfei Bai

title: Pybullet, a python module for physics simulation for games, robotics and machine learning, 2016

authors:
Yannis Flet-Berliac
Philippe Preux

title: Merl: Multi-head reinforcement learning

venue: In Deep Reinforcement Learning Workshop,

title: Only relevant information matters: Filtering out noisy samples to boost rl

venue: In International Joint Conference on Artificial Intelligence,

authors:
Yannis Flet-Berliac
Johan Ferret
Olivier Pietquin
Philippe Preux
Matthieu Geist

title: Adversarially guided actor-critic

venue: In International Conference on Learning Representations,

authors:
Evan Greensmith
Peter L Bartlett
Jonathan Baxter

title: Variance reduction techniques for gradient estimates in reinforcement learning

venue: Journal of Machine Learning Research,

authors:
Shixiang Gu
Timothy Lillicrap
Ilya Sutskever
Sergey Levine

title: Continuous deep q-learning with model-based acceleration

venue: In International Conference on Machine Learning,

authors:
Tuomas Haarnoja
Aurick Zhou
Pieter Abbeel
Sergey Levine

title: Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor

authors:
Andrew Ilyas
Logan Engstrom
Shibani Santurkar
Dimitris Tsipras
Firdaus Janoos
Larry Rudolph
Aleksander Madry

title: A closer look at deep policy gradients

authors:
Max Jaderberg
Volodymyr Mnih
Wojciech Marian Czarnecki
Tom Schaul
Joel Z Leibo
David Silver
Koray Kavukcuoglu

title: Reinforcement learning with unsupervised auxiliary tasks

venue: arXiv preprint arXiv:1611.05397,

authors:
Rie Johnson
Tong Zhang

title: Accelerating stochastic gradient descent using predictive variance reduction

title: Learning to achieve goals

venue: In IJCAI,

authors:
Sham Kakade
John Langford

title: Approximately optimal approximate reinforcement learning

authors:
Bilal Kartal
Pablo Hernandez-Leal
Matthew E Taylor

title: Terminal prediction as an auxiliary task for deep reinforcement learning

venue: In AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment,

authors:
Timothy P Lillicrap
Jonathan J Hunt
Alexander Pritzel
Nicolas Heess
Tom Erez
Yuval Tassa
David Silver
Daan Wierstra

title: Continuous control with deep reinforcement learning

authors:
Kaixiang Lin
Jiayu Zhou

title: Ranking policy gradient

authors:
Hao Liu
Yihao Feng
Yi Mao
Dengyong Zhou
Jian Peng
Qiang Liu

title: Action-dependent control variates for policy optimization via stein identity

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Alex Graves
Ioannis Antonoglou
Daan Wierstra
Martin Riedmiller

title: Playing atari with deep reinforcement learning

venue: arXiv preprint arXiv:1312.5602,

authors:
Volodymyr Mnih
Adria Puigdomenech Badia
Mehdi Mirza
Alex Graves
Timothy Lillicrap
Tim Harley
David Silver
Koray Kavukcuoglu

title: Asynchronous methods for deep reinforcement learning

authors:
H. Namkoong
J.C. Duchi

title: Variance-based regularization with convex objectives

authors:
Jan Peters
Katharina Mulling
Yasemin Altun

title: Relative entropy policy search

venue: In AAAI Conference on Artificial Intelligence,

authors:
T Pham-Gia
TL Hung

title: The mean and median absolute deviations

venue: Mathematical and Computer Modelling,

title: Markov Decision Processes: Discrete Stochastic Dynamic Programming

title: Developmental robotics, optimal artificial curiosity, creativity, music, and the fine arts

venue: Connection Science,

authors:
J. Schulman
S. Levine
P. Abbeel
M. Jordan
P. Moritz

title: Trust region policy optimization

authors:
J. Schulman
F. Wolski
P. Dhariwal
A. Radford
O. Klimov

title: Proximal policy optimization algorithms

authors:
John Schulman
Philipp Moritz
Sergey Levine
Michael Jordan
Pieter Abbeel

title: High-dimensional continuous control using generalized advantage estimation

authors:
David Silver
Guy Lever
Nicolas Heess
Thomas Degris
Daan Wierstra
Martin Riedmiller

title: Deterministic policy gradient algorithms

authors:
Richard S Sutton
David A McAllester
Satinder P Singh
Yishay Mansour

title: Policy gradient methods for reinforcement learning with function approximation

authors:
P. Thodoroff
A. Durand
J. Pineau
D. Precup

title: Temporal regularization for markov decision process

authors:
E. Todorov
T. Erez
Y. Tassa

title: Mujoco: A physics engine for model-based control

venue: In IEEE/RSJ International Conference on Intelligent Robots and Systems,

title: Adaptive ε-greedy exploration in reinforcement learning based on value differences

venue: In Annual Conference on Artificial Intelligence,

authors:
George Tucker
Surya Bhupatiraju
Shixiang Gu
Richard Turner
Zoubin Ghahramani
Sergey Levine

title: The mirage of action-dependent baselines in reinforcement learning

authors:
Hado Van Hasselt
Arthur Guez
David Silver

title: Deep reinforcement learning with double qlearning

venue: arXiv preprint arXiv:1509.06461,

authors:
Ziyu Wang
Tom Schaul
Matteo Hessel
Hado Hasselt
Marc Lanctot
Nando Freitas

title: Dueling network architectures for deep reinforcement learning

title: Simple statistical gradient-following algorithms for connectionist reinforcement learning

venue: Machine Learning,

authors:
Ronald J Williams
Jing Peng

title: Function optimization using connectionist reinforcement learning algorithms

authors:
Cathy Wu
Aravind Rajeswaran
Yan Duan
Vikash Kumar
Alexandre M Bayen
Sham Kakade
Igor Mordatch
Pieter Abbeel

title: Variance reduction for policy gradient with action-dependent factorized baselines

authors:
Tingting Zhao
Gang Niu
Ning Xie
Jucheng Yang
Masashi Sugiyama

title: Regularized policy gradients: direct variance reduction in policy gradient estimation

venue: In Asian Conference on Machine Learning,

title: 2020) indicates that commonly used algorithms fail to fit the true value function. However, this does not rule out the usefulness of the approach but rather begs for more questioning of the true effect of such biased baselines

heading: 1 INTRODUCTION

text:
Model-free deep reinforcement learning (RL) has been successfully used in a wide range of problem domains, ranging from teaching computers to control robots to playing sophisticated strategy games (Silver et al., 2014; Schulman et al., 2016; Lillicrap et al., 2016; Mnih et al., 2016). Stateof-the-art policy gradient algorithms currently combine ingenious learning schemes with neural networks as function approximators in the so-called actor-critic framework (Sutton et al., 2000; Schulman et al., 2017; Haarnoja et al., 2018). While such methods demonstrate great performance in continuous control tasks, several discrepancies persist between what motivates the conceptual framework of these algorithms and what is implemented in practice to obtain maximum gains.
For instance, research aimed at improving the learning of value functions often restricts the class of function approximators through different assumptions, then propose a critic formulation that allows for a more stable policy gradient. However, new studies (Tucker et al., 2018; Ilyas et al., 2020) indicate that state-of-the-art policy gradient methods (Schulman et al., 2015; 2017) fail to fit the true value function and that recently proposed state-action-dependent baselines (Gu et al., 2016; Liu et al., 2018; Wu et al., 2018) do not reduce gradient variance more than state-dependent ones.
These findings leave the reader skeptical about actor-critic algorithms, suggesting that recent research tends to improve performance by introducing a bias rather than stabilizing the learning. Consequently, attempting to find a better baseline is questionable, as critics would typically fail to fit it (Ilyas et al., 2020). In Tucker et al. (2018), the authors argue that “much larger gains could be achieved by instead improving the accuracy of the value function”. Following this line of thought, we are interested in ways to better approximate the value function. One approach addressing this issue is to put more focus on relative state-action values, an idea introduced in the literature on advantage reinforcement
∗Equal contribution.
learning (Harmon & Baird III) followed by works on dueling (Wang et al., 2016) neural networks. More recent work (Lin & Zhou, 2020) also suggests that considering the relative action values, or more precisely the ranking of actions in a state leads to better policies. The main argument behind this intuition is that it suffices to identify the optimal actions to solve a task. We extend this principle of relative action value with respect to the mean value to cover both state and state-action-value functions with a new objective for the critic: minimizing the variance of residual errors.
In essence, this modified loss function puts more focus on the values of states (resp. state-actions) relative to their mean value rather than their absolute values, with the intuition that solving a task corresponds to identifying the optimal action(s) rather than estimating the exact value of each state. In summary, this paper:
• Introduces Actor with Variance Estimated Critic (AVEC), an actor-critic method providing a new training objective for the critic based on the residual variance.
• Provides evidence for the improvement of the value function approximation as well as theoretical consistency of the modified gradient estimator.
• Demonstrates experimentally that AVEC, when coupled with state-of-the-art policy gradient algorithms, yields a significant performance boost on a set of challenging tasks, including environments with sparse rewards.
• Provides empirical evidence supporting a better fit of the true value function and a substantial stabilization of the gradient.

heading: 2 RELATED WORK

text:
Our approach builds on three lines of research, of which we give a quick overview: policy gradient algorithms, regularization in policy gradient methods, and exploration in RL.
Policy gradient methods use stochastic gradient ascent to compute a policy gradient estimator. This was originally formulated as the REINFORCE algorithm (Williams, 1992). Kakade & Langford (2002) later created conservative policy iteration and provided lower bounds for the minimum objective improvement. Peters et al. (2010) replaced regularization by a trust region constraint to stabilize training. In addition, extensive research investigated methods to improve the stability of gradient updates, and although it is possible to obtain an unbiased estimate of the policy gradient from empirical trajectories, the corresponding variance can be extremely high. To improve stability, Weaver & Tao (2001) show that subtracting a baseline (Williams, 1992) from the value function in the policy gradient can be very beneficial in reducing variance without damaging the bias. However, in practice, these modifications on the actor-critic framework usually result in improved performance without a significant variance reduction (Tucker et al., 2018; Ilyas et al., 2020). Currently, one of the most dominant on-policy methods are proximal policy optimization (PPO) (Schulman et al., 2017) and trust region policy optimization (TRPO) (Schulman et al., 2015), both of which require new samples to be collected for each gradient step. Another direction of research that overcomes this limitation is off-policy algorithms, which therefore benefit from all sample transitions; soft actor-critic (SAC) (Haarnoja et al., 2018) is one such approach achieving state-of-the-art performance.
Several works also investigate regularization effects on the policy gradient (Jaderberg et al., 2016; Namkoong & Duchi, 2017; Kartal et al., 2019; Flet-Berliac & Preux, 2019; 2020); it is often used to shift the bias-variance trade-off towards reducing the variance while introducing a small bias. In RL, regularization is often used to encourage exploration and takes the form of an entropy term (Williams & Peng, 1991; Schulman et al., 2017). Moreover, while regularization in machine learning generally consists in smoothing over the observation space, in the RL setting, Thodoroff et al. (2018) show that it is possible to smooth over the temporal dimension as well. Furthermore, Zhao et al. (2016) analyze the effects of a regularization using the variance of the policy gradient (the idea is reminiscent of SVRG descent (Johnson & Zhang, 2013)) which proves to provide more consistent policy improvements at the expense of reduced performance. In contrast, as we will see later, AVEC does not change the policy network optimization procedure nor involves any additional computational cost.
Exploration has been studied under different angles in RL, one common strategy is -greedy, where the agent explores with probability by taking a random action. This method, just like entropy regularization, enforces uniform exploration and has achieved recent success in game playing en-
vironments (Mnih et al., 2013; Van Hasselt et al., 2015; Mnih et al., 2016). On the other hand, for most policy-based RL, exploration is a natural component of any algorithm following a stochastic policy, choosing sub-optimal actions with non-zero probability. Furthermore, policy gradient literature contains exploration methods based on uncertainty estimates of values (Kaelbling, 1993; Tokic, 2010), and algorithms which provide intrinsic exploration or curiosity bonus to encourage exploration (Schmidhuber, 2006; Bellemare et al., 2016; Flet-Berliac et al., 2021).
While existing research may share some motivations with our method, no previous work in RL applies the variance of residual errors as an objective loss function. In the context of linear regression, Brown (1947) considers a median-unbiased estimator minimizing the risk with respect to the absolutedeviation loss function (Pham-Gia & Hung, 2001) (similar in spirit to the variance of residual errors), their motivation is nonetheless different to ours. Indeed, they seek to be robust to outliers whereas, when considering noiseless RL problems, one usually seeks to capture those (sometimes rare) signals corresponding to the rewards.

heading: 3 PRELIMINARIES

heading: 3.1 BACKGROUND AND NOTATIONS

text:
We consider an infinite-horizon Markov Decision Problem (MDP) with continuous states s ∈ S, continuous actions a ∈ A, transition distribution st+1 ∼ P(st, at) and reward function rt ∼ R(st, at). Let πθ(a|s) denote a stochastic policy with parameter θ, we restrict policies to being Gaussian distributions. In the following, π and πθ denote the same object. The agent repeatedly interacts with the environment by sampling action at ∼ π(.|st), receives reward rt and transitions to a new state st+1. The objective is to maximize the expected sum of discounted rewards:
J(π) , Eτ∼π [ ∞∑ t=0 γtr (st, at) ] , (1)
where γ ∈ [0, 1) is a discount factor (Puterman, 1994), and τ = (s0, a0, r0, s1, a1, r1, . . . ) is a trajectory sampled from the environment using policy π. We denote the value of a state s in the MDP framework while following a policy π by V π(s) , Eτ∼π [ ∑∞ t=0 γ
tr (st, at) |s0 = s] and the value of a state-action pair of performing action a in state s and then following policy π by Qπ(s, a) , Eτ∼π [ ∑∞ t=0 γ
tr (st, at) |s0 = s, a0 = a]. Finally, the advantage function which quantifies how an action a is better than the average action in state s is denoted Aπ(s, a) , Qπ(s, a)− V π(s).

heading: 3.2 CRITICS IN DEEP POLICY GRADIENTS

text:
In this section, we consider the case where the value functions are learned using function estimators and then used in an approximation of the gradient. Without loss of generality, we consider the algorithms that approximate the state-value function V . The analysis holds for algorithms that approximate the state-action-value function Q. Let fφ : S → R be an estimator of V̂ π with φ its parameter. fφ is traditionally learned through minimizing the mean squared error (MSE) against V̂ π . At iteration k, the critic minimizes:
LAC = Es [( fφ(s)− V̂ πθk (s) )2] , (2)
where the states s are collected under policy πθk , and V̂ πθk (s) is an empirical estimate of V (see Section 4.3 for details). Similarly, using fφ : S ×A → R instead, one can fit an empirical target Q̂π .

heading: 4 METHOD: ACTOR WITH VARIANCE ESTIMATED CRITIC

text: In this section, we introduce AVEC and discuss its correctness, motivations and implementation.

heading: 4.1 DEFINING AN ALTERNATIVE CRITIC

text:
Recent work (Ilyas et al., 2020) empirically demonstrates that while the value network succeeds in the supervised learning task of fitting V̂ π (resp. Q̂π), it does not fit V π (resp. Qπ). We address this
deficiency in the estimation of the critic by introducing an alternative value network loss. Following empirical evidence indicating that the problem is the approximation error and not the estimator per se, AVEC adopts a loss that can provide a better approximation error, and yields better estimators of the value function (as will be shown in Section 5.3). At update k:
LAVEC = Es [( (fφ(s)− V̂ πθk (s))− Es [ fφ(s)− V̂ πθk (s) ])2] , (3)
with states s collected using πθk . Note that the gradient flows in fφ twice using Eq. 3. Then, we define our bias-corrected estimator: gφ : S → R such that gφ(s) = fφ(s) + Es[V̂ πθk (s) − fφ(s)]. Analogously to Eq. 3, we define an alternative critic for the estimation of Qπ by replacing V̂ π by Q̂π and fφ(s) by fφ(s, a).
Proposition (AVEC Policy Gradient). If fφ : S × A → R satisfies the parameterization assumption (Sutton et al., 2000) then gφ provides an unbiased policy gradient:
∇θJ (πθ) = E(s,a)∼πθ [∇θ log(πθ(s, a))gφ(s, a)] .
Proof. See Appendix A. This result also holds for the estimation of V πθ with fφ : S → R.

heading: 4.2 BUILDING MOTIVATION

text:
Here, we present the intuition behind using AVEC for actor-critic algorithms. Tucker et al. (2018) and Ilyas et al. (2020) indicate that the approximation error ‖V̂ π − V π‖ is problematic, suggesting that the variance of the empirical targets V̂ π(st) is high. Using LAVEC, our approach reduces the variance term of the MSE (or distance to V π) but mechanistically also increases the bias. Our intuition is that since the bias is already quite substantial (Ilyas et al., 2020), it may be possible to reduce the variance enough so that even though the bias increases, the total MSE reduces.
State-value function estimation. In this case, optimizing the critic with LAVEC can be interpreted as fitting V̂ ′π(s) = V̂ π(s) − Es′ [V̂ π(s′)] using the MSE. We show that the targets V̂ ′π are better estimations of V ′π(s) = V π(s) − Es′ [V π(s′)] than V̂ π are of V π. To illustrate this, consider T independent random variables (Xi)i∈{1,...,T}. We denote X ′i = Xi − 1T ∑T j=1Xj and V(X) the variance of X . Then, V (X ′i) = V (Xi) − 2T V (Xi) + 1 T 2 ∑T j=1 V (Xj) and V(X ′i) < V(Xi)
as long as ∀i 1T ∑T j=1 V(Xj) < 2V(Xi), or more generally when state-values are not strongly negatively correlated1 and not very discordant. This entails that V̂ ′π has a more compact span, and is consequently easier to fit. This analysis shows that the variance term of the MSE is reduced compared to traditional actor-critic algorithms, but does not guarantee it counterbalances the bias increase. Nevertheless, in practice, the bias is so high that the difference due to learning with AVEC is only marginal and the total MSE decreases. We empirically demonstrate this claim in Section 5.3.
0 2 4 6 8 0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5 MSE
Var Initial
Figure 1: Comparison of simple models derived when LAVEC is used instead of the MSE.
State-action-value function estimation. In this case, Eq. 3 translates into replacing V̂ π(s) by Q̂π(s, a) and fφ(s) by fφ(s, a) and the rationale for optimizing the residual variance of the value function instead of the full MSE becomes more straightforward: the practical use of the Q-function is to disentangle the relative values of actions for each state (Sutton et al., 2000). AVEC’s effect on relative values is illustrated in a didactic regression with one variable example in Fig. 1 where grey markers are observations and the blue line is our current estimation. Minimizing the MSE, the line is expected to move
towards the orange one in order to reduce errors uniformly. Minimizing the residual variance, it
1Greensmith et al. (2004) analyze the dependent case: in general, weakly dependent variables tend to concentrate more than independent ones.
is expected to move near the red one. In fact, LAVEC tends to further penalize observations that are far away from the mean, implying that AVEC allows a better recovery of the “shape” of the target near extrema. In particular, we see in the figure that the maximum and minimum observation values are quickly identified. Would the approximators be linear and the target state-values independent, the two losses become equivalent since ordinary least squares would provide minimum-variance mean-unbiased estimation.
It should be noted that, as in all the works related to ours, we consider noiseless tasks, i.e. the transition matrix is deterministic. As such, there are no outliers and extreme state-action values correspond to learning signals. In this context, high estimation errors indicate where (in the state or action-state space) the training of the value function should be improved.

heading: 4.3 IMPLEMENTATION

text:
We apply this new formulation to three of the most dominant deep policy gradient methods to study whether it results in a better estimation of the value function. A better estimation of the value function implies better policy improvements. We now describe how AVEC incorporates its residual variance objective into the critics of PPO (Schulman et al., 2017), TRPO (Schulman et al., 2015) and SAC (Haarnoja et al., 2018). Let B be a batch of transitions. In PPO and TRPO, AVEC modifies the learning of Vφ (line 12 of Algorithm 1) using:
L1AVEC (φ) = Es∼B [ (fφ (s)− V̂ π (s))− Es∼B [ fφ (s)− V̂ π (s) ] ]2 ,
then Vφ = fφ(s) + Es∼B[V̂ π(s) − fφ(s)], where V̂ π (st) = fφold(st) + At such that fφold(st) are the estimates given by the last value function and At is the advantage of the policy, i.e. the returns minus the expected values (At is often estimated using generalized advantage estimation (Schulman et al., 2016). In SAC, AVEC modifies the objective function of (Qφi)i=1,2 (line 13 of Algorithm 2 in Appendix C) using:
L2AVEC (φi) = E(s,a)∼B [ (fφi(s, a)− Q̂π(s, a))− E(s,a)∼B [ fφi(s, a)− Q̂π(s, a) ] ]2 ,
then Qφi = fφi(s, a) + E(s,a)∼B[Q̂π(s, a)− fφi(s, a)], where Q̂π(s, a) is estimated using temporal difference (see Haarnoja et al. (2018)): Q̂π(st, at) = r(st, at) + γEst+1∼π[Vψ̄(st+1)] with ψ̄ the value function parameter (see Algorithm 2). The reader may have noticed that L1AVEC and L2AVEC slightly differ from Eq. 3. The residual variance of the value function (LAVEC) is not tractable since a priori state-values are dependent and their joint law is unknown. Consequently, in practice, we use the empirical variance proxy assuming independence (cf. Appendix D). Greensmith et al. (2004) provide some support for this approximation by showing that weakly dependent variables tend to concentrate more than independent ones. Finally, notice that AVEC does not modify any other part of the considered algorithms whatsoever, which makes its implementation straightforward and keeps the same computational complexity.

heading: 5 EXPERIMENTAL STUDY

text:
In this section, we conduct experiments along four orthogonal directions. (a) We validate the superiority of AVEC compared to the traditional actor-critic training. (b) We evaluate AVEC in environments with sparse rewards. (c) We clarify the practical implications of using AVEC by examining the bias in both the empirical and true value function estimations as well as the variance in the empirical gradient. (d) We provide an ablation analysis and study the bias-variance trade-off in the critic by considering two continuous control tasks. We point out that a comparison to variance-reduction methods is not considered in this paper: Tucker et al. (2018) demonstrated that their implementations diverge from the unbiased methods presented in the respective papers and unveiled that not only do they fail to reduce the variance of the gradient, but that their unbiased versions do not improve performance either. Note that in all experiments we choose the hyperparameters providing the best performance for the considered methods which can only penalyze AVEC (cf. Appendix E). In all the figures hereafter (except Fig. 3c and 3d), lines are average performances and shaded areas represent one standard deviation.
5.1 CONTINUOUS CONTROL
Algorithm 1 AVEC coupled with PPO or TRPO. JALGO denotes the policy loss of either algorithm (described in Schulman et al. (2017; 2015)).
1: Input parameters: λπ ≥ 0, λV ≥ 0 2: Initialize policy parameter θ and value func-
tion parameter φ 3: for each update step do 4: batch B ← ∅ 5: for each environment step do 6: at ∼ πθ(st) 7: st+1 ∼ P (st, at) 8: B ← B ∪ {(st, at, rt, st+1)} 9: end for
10: for each gradient step do 11: θ ← θ − λπ∇̂θJALGO(πθ) 12: φ← φ− λV ∇̂φL1AVEC (φ) 13: end for 14: end for For ease of comparison with other methods, we evaluate AVEC on the MuJoCo (Todorov et al., 2012) and the PyBullet (Coumans & Bai, 2016) continuous control benchmarks (see Appendix G for details) using OpenAI Gym (Brockman et al., 2016). Note that the PyBullet versions of the locomotion tasks are harder than the MuJoCo equivalents2. We choose a representative set of tasks for the experimental evaluation; their action and observation space dimensions are reported in Appendix H. We assess the benefits of AVEC when coupled with the most prominent policy gradient algorithms, currently state-of-the-art methods: PPO (Schulman et al., 2017) and TRPO (Schulman et al., 2015), both on-policy methods, and SAC (Haarnoja et al., 2018), an off-policy maximum entropy deep RL algorithm. We provide the list of hyperparameters and further implementation details in Appendix D and E.
Table 1 reports the results while Fig. 2 and 8 show the total average return for SAC and PPO. TRPO results are provided in Appendix F for readability. When coupled with SAC and PPO, AVEC brings very significant improvement (on average +26% for SAC and +39% for PPO) in the performance of the policy gradient algorithms, improvement which is consistent across tasks. As for TRPO, while the improvement in performance is less striking, AVEC still manages to be more efficient in terms of sampling in all tasks. Overall, AVEC improves TRPO, PPO and SAC in terms of performance and efficiency. This does not imply that our method would also improve other policy gradient methods that use the traditional actor-critic framework, but since we evaluate our method coupled with three of the best performing on- and off-policy algorithms, we believe that these experiments are sufficient to prove the relevance of AVEC. Furthermore, in our experiments we do not seek the best hyperparameters for the AVEC variants, we simply adopt the parameters allowing us to optimally reproduce the baselines. Alternatively, if one seeks to evaluate AVEC independently of a considered baseline, further hyperparameter tuning should produce better results. Notice that since no additional calculations are needed in AVEC’s implementation, computational complexity remains unchanged.

heading: 5.2 SPARSE REWARD SIGNALS

text:
Domains with sparse rewards are challenging to solve with uniform exploration as agents receive no feedback on their actions before starting to collect rewards. In such conditions AVEC performs better, suggesting that the shape of the value function is better approximated, encouraging exploration.
2Bullet Physics SDK GitHub Issue.
The relative value estimate of an unseen state is more accurate: in Section 4.2, AVEC identifies extreme state-values (e.g., non-zero rewards in tasks with sparse rewards) faster. In Fig. 3a and 3b, we report the performance of AVEC in the Acrobot and MountainCar environments: both have sparse rewards. AVEC enhances TRPO and PPO in both experiments. When PPO and AVEC-PPO both reach the best possible performance, AVEC-PPO exhibits better sample efficiency. Fig. 3c and 3d illustrate how the agent improves its exploration strategy in MountainCar: while the PPO agent remains stuck at the bottom of the hill (red), the graph suggest that AVEC-PPO learns the difficult locomotion principles in the absence of rewards and visits a much larger part of the state space (green).
This improved performance in sparse environments can be explained by the fact that AVEC is able to pick up on experienced positive reward more easily. Moreover, the reconstructed shape of the value function is more accurate around such rewarding states, which pushes the agent to explore further around experienced states with high values.

heading: 5.3 ANALYSIS OF THE VARIANCE ESTIMATED CRITIC

text:
In order to further validate AVEC, we evaluate the performance of the value network in more detail: we examine (a) the estimation error (distance to the empirical target), (b) the approximation error (distance to the true target) and (c) the empirical variance of the gradient. (a,b) should be put into perspective with the conclusions of Ilyas et al. (2020) where it is found that the critic only fits the empirical value function but not the true one. (c) should be placed in light of Tucker et al. (2018) highlighting a failure of recently proposed state-action-dependent baselines to reduce the variance.
Learning the Empirical Target. In Fig. 4, we report the quality of fit (MSE) of the empirical target V̂ π in the methods PPO and AVEC-PPO in the AntBullet and HalfCheetahBullet tasks.
0.0 0.2 0.4 0.6 0.8 1.0 Timesteps 1e6
0
100
200
300
400
D is
ta nc
e to
e m
pi ric
al V
-fu nc
tio n
AntBullet AVEC-PPO PPO
0.0 0.2 0.4 0.6 0.8 1.0 Timesteps 1e6
100
200
300
400
500
D is
ta nc
e to
e m
pi ric
al V
-fu nc
tio n
HalfCheetahBullet AVEC-PPO PPO
Figure 4: L2 distance to V̂ π .
We observe that PPO better fits the empirical target than when equipped with AVEC, which is to be expected since vanilla PPO optimizes the MSE directly. This result put aside the remarkable improvement in the performance of AVEC-PPO (Fig. 2) suggests that AVEC might be a better estimator of the true value function. We examine this claim below because if true, it
would indicate that it is indeed possible to simultaneously improve the performance of the agents and the stability of the method.
Learning the True Target. A fundamental premise of policy gradient methods is that optimizing the objective based on an empirical estimation of the value function leads to a better policy. Which is why we investigate the quality of fit of the true target. To approximate the true value function, we fit the returns sampled from the current policy using a large number of transitions (3 · 105). Fig. 5 shows that gφ is far closer to the true value function half of the time (horizon is 106) than the estimator obtained
with MSE, then as close to it. Comparing Fig. 5 with Fig. 4, we see that the distance to the true target is close to the estimation error for AVEC-PPO, while for PPO, it is at least two orders of magnitude higher at all times. We further investigate these results in Fig. 9 in Appendix B.2 where we study the variation of the squared bias and variance components of the MSE to the true target (MSE = Var + Bias2). We find, as expected, that using AVEC reduces the variance term significantly while slightly increasing the bias term, which Fig. 5 confirms is negligible since the total MSE is substantially reduced (‖gφ(AVEC)− V π‖2 ≤ ‖Vφ(PPO)− V π‖2) where Vφ(PPO) is the value function estimator in PPO. For completeness, we also analyze the distance to the true target for the Q-function estimator in SAC and AVEC-SAC in AntBullet and HalfCheetahBullet in Appendix B.3, with similar results and interpretation. We conclude that AVEC improves the value function approximation and we expect that the gradient is more stable.
Empirical Variance Reduction. We choose to study the gradient variance using the average pairwise cosine similarity metric as it allows a comparison with Ilyas et al. (2020), with which we share the same experimental setup and scales. Fig. 6 shows that AVEC yields a higher average (10 batches per iteration) pairwise cosine similarity, which means closer batch-estimates of
the gradient and, in turn, indicates smaller gradient variance. Further analysis with additional tasks is included in Appendix B.4. The variance reduction effect observed in several environments suggests that AVEC is the first method since the introduction of the value function baseline to further reduce the variance of the gradient and improve performance.

heading: 5.4 ABLATION STUDY

text:
In this section, we examine how changing the relative importance of the bias and the residual variance in the loss of the value network affects learning. For this study, we choose difficult tasks of PyBullet and use PPO because it is more efficient than TRPO and requires less computations than SAC. For an estimator ŷn of (yi)i∈{1,...,n}, we write Bias = 1n ∑n i=1(ŷi − yi) and Var =
1 n−1 ∑n i=1(ŷi − yi −Bias)2. Consequently: MSE = Var + Bias
2. We denote Lα = Var + αBias2, with α ∈ R. In Fig. 7, Bias-α means that we use Lα and Var-α means that we use L 1
α . We observe
that while no consistent order on the choices of α is identified, AVEC seems to outperform all other weightings. Note that, for readability purposes, the graphs have been split and the curves of AVEC-PPO and PPO are the same in Fig. 7a and 7c, and in Fig. 7b and 7d. A more extensive hyperparameter
study with more α values might provide even higher performances, nevertheless we believe that the stability of an algorithm is crucial for a reliable performance. As such, the tuning of hyperparameters to achieve good results should remain mild.

heading: 6 DISCUSSION

text:
In this work, we introduce a new training objective for the critic in actor-critic algorithms to better approximate the true value function. In addition to being well-motivated by recent studies on the behaviour of deep policy gradient algorithms, we demonstrate that this modification is both theoretically sound and intuitively supported by the need to improve the approximation error of the critic. The application of Actor with Variance Estimated Critic (AVEC) to state-of-the-art policy gradient methods produces considerable gains in performance (on average +26% for SAC and +39% for PPO) over the standard actor-critic training, without any additional hyperparameter tuning.
First, for SAC-like algorithms where the critic learns a state-action-value function, our results strongly suggest that state-actions with extreme values are identified more quickly. Second, for PPO-like methods where the critic learns the state-values, we show that the variance of the gradient is reduced and empirically demonstrate that this is due to a better approximation of the state-values. In sparse reward environments, the theoretical intuition behind a variance estimated critic is more explicit and is also supported by empirical evidence. In addition to corroborating the results in Ilyas et al. (2020) proving that the value estimator fails to fit V π, we propose a method that succeeds in improving both the sample complexity and the stability of prominent actor-critic algorithms. Furthermore, AVEC benefits from its simplicity of implementation since no further assumptions are required (such as horizon awareness Tucker et al. (2018) to remedy the deficiency of existing variance-reduction methods) and the modification of current algorithms represents only a few lines of code.
In this paper, we have demonstrated the benefits of a more thorough analysis of the critic objective in policy gradient methods. Despite our strongly favourable results, we do not claim that the residual variance is the optimal loss for the state-value or the state-action-value functions, and we note that the design of comparably superior estimators for critics in deep policy gradient methods merits further study. In future work, further analysis of the bias-variance trade-off and extension of the results to stochastic environments is anticipated; we consider the problem of noise separation in the latter, as this is the first obstacle to accessing the variance and distinguishing extreme values from outliers.

heading: B ADDITIONAL EXPERIMENTS

text:
B.1 CONTINUOUS CONTROL: WALKER2D
Fig. 8 shows the total average return for AVEC coupled with SAC and PPO on the Walker2d task. Similar to considered other continuous control tasks from MuJoCo and PyBullet, AVEC brings a significant performance improvement (+26% for SAC and +33% for PPO), confirming the generality of our approach.
B.2 VARIATION OF THE BIAS AND VARIANCE TERMS: PPO
In Fig. 9, we show the variation of the bias and variance terms in the MSE between the estimators (of AVEC-PPO and PPO) and the true target: E[‖gφ − V π‖22] = Bias(AVEC)2 + Var(AVEC) and E[‖Vφ(PPO)− V π‖22] = Bias(PPO)2 + Var(PPO) where Vφ(PPO) is the value function estimator in PPO. We observe that the variance reduction is more substantial than that of the bias. Using those results and Fig. 5 showing that the distance of the estimator to V π is lower when using AVEC confirms that the variance reduction effect counterbalances the bias increase. Note that the % Variation of the Var term is always negative in our experiments, and that the shaded areas that suggest otherwise are merely due to a false assumption of symmetrical deviations, itself due to the assumption of Gaussianity needed to construct confidence intervals.
target: %Variation(Bias) = Bias
2(AVEC-PPO)−Bias2(PPO) Bias2(PPO) and %Variation(Var) = Var(AVEC-PPO)−Var(PPO) Var(PPO) .
X-axis: we run PPO and AVEC-PPO and for every t ∈ {1, 2, 4, 6, 9} · 105, we stop training, use the current policy to interact with the environment for 3 · 105 transitions, and use these transitions to estimate the true value function. Lines are average variations and shaded areas represent one standard deviation (5 seeds).
B.3 LEARNING THE TRUE TARGET: SAC
In Fig. 10, we compare the error between the Q-function estimator and the true Q-function for SAC and AVEC-SAC in AntBullet and HalfCheetahBullet. We note a modest but consistent reduction in this error when using AVEC coupled with SAC, echoing the significant performance gains in Fig. 2.
B.4 VARIANCE REDUCTION
In Fig. 11, we study the empirical variance of the gradient in measuring the average pairwise cosine similarity (10 gradient measurements) in two additional tasks: HopperBullet and Walker2DBullet. We also vary the trajectory size used in the estimation of the gradient.
C IMPLEMENTATION OF AVEC COUPLED WITH SAC
In Algorithm 2, JV is the squared residual error objective to train the soft value function. See Haarnoja et al. (2018) for further details and notations about SAC, not directly relevant here.
Algorithm 2 AVEC coupled with SAC. 1: Input parameters: β ∈ [0, 1], λV ≥ 0, λQ ≥ 0, λπ ≥ 0 2: Initialize policy parameter θ, value function parameter ψ and ψ̄ and Q-functions parameters φ1
and φ2 3: D ← ∅ 4: for each iteration do 5: for each step do 6: at ∼ πθ(at|st) 7: st+1 ∼ P (st, at) 8: D ← D ∪ {(st, at, rt, st+1)} 9: end for
10: for each gradient step do 11: sample batch B from D

heading: 12: ψ ← ψ − λV ∇̂ψJV (ψ)

text:
13: φi ← φi − λQ∇̂φiL2AVEC (φi) for i ∈ {1, 2} 14: θ ← θ − λπ∇̂θJ(πθ) 15: ψ̄ ← βψ + (1− β)ψ̄ 16: end for 17: end for
D IMPLEMENTATION DETAILS
Theoretically, LAVEC is defined as the residual variance of the value function (cf. Eq. 3). However, state-values for a non-optimal policy are dependent and the variance is not tractable without access to the joint law of state-values. Consequently, to implement AVEC in practice we use the best-known proxy at hand, which is the empirical variance formula assuming independence:
LAVEC = 1
T − 1 T∑ t=1 (( fφ(st)− V̂ π(st) ) − 1 T T∑ t=1 ( fφ(st)− V̂ π(st) ))2 ,
where T is the size of the sampled trajectory.

heading: E EXPERIMENT DETAILS

text:
In all experiments we choose to use the same hyperparameter values for all tasks as the bestperforming ones reported in the literature or in their respective open source implementation documentation. We thus ensure the best performance for the conventional actor-critic framework. In other words, since we are interested in evaluating the impact of this new critic, everything else is kept as is. This experimental protocol may not benefit AVEC.
In Table 2, 3 and 4, we report the list of hyperparameters common to all continuous control experiments.
F COMPARATIVE EVALUATION OF AVEC WITH TRPO
In order to evaluate the performance gains in using AVEC instead of the usual actor-critic framework, we produce some additional experiments with the TRPO (Schulman et al., 2015) algorithm. Fig. 12 shows the learning curves while Table 5 reports the results.

heading: H DIMENSIONS OF STUDIED TASKS

heading: G ENVIRONMENTS DETAILS

title: LEARNING VALUE FUNCTIONS IN DEEP POLICY GRA-