Count-Based Exploration in Feature Space for Reinforcement Learning

By Jarryd Martin, Suraj Narayanan Sasikumar, Tom Everitt, Marcus Hutter. 2017

132 citations recorded by the source corpus.

We introduce a new count-based optimistic exploration algorithm for Reinforcement Learning (RL) that is feasible in environments with high-dimensional state-action spaces. The success of RL algorithms in these domains depends crucially on generalisation from limited training experience. Function approximation techniques enable RL agents to generalise in order to estimate the value of unvisited states, but at present few methods enable generalisation regarding uncertainty. This has prevented the combination of scalable RL algorithms with efficient exploration strategies that drive the agent to reduce its uncertainty. We present a new method for computing a generalised state visit-count, which allows the agent to estimate the uncertainty associated with any state. Our \phi-pseudocount achieves generalisation by exploiting same feature representation of the state space that is used for value function approximation. States that have less frequently observed features are deemed more uncertain. The \phi-Exploration-Bonus algorithm rewards the agent for exploring in feature space rather than in the untransformed state space. The method is simpler and less computationally expensive than some previous proposals, and achieves near state-of-the-art results on high-dimensional RL benchmarks.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents (2017, methodology): “We often see episodes terminating when the game is over (e.g., Hausknecht, Lehman, Miikkulainen, & Stone, 2014; Liang et al., 2016; Lipovetzky, Ramirez, & Geffner, 2015; Martin et al., 2017), as well as when the agent loses a life (e.”
Go-Explore: a New Approach for Hard-Exploration Problems (2019, background): “Montezuma’s Revenge has become an important benchmark for exploration algorithms (including intrinsic motivation algorithms) [4, 16, 32–39] because precise sequences of hundreds of actions must be taken in between receiving rewards.”
Semantic Exploration from Language Abstractions and Pretrained Representations (2022, background): “Exploration in RL Classical exploration strategies include ✏-greedy action selection [51], statecounting [49, 4, 32, 30, 3], curiosity driven exploration [44], and intrinsic motivation methods [36].”
The Benchmark Lottery (2021, background): “…publications episodes terminate when the game is over [Bellemare et al., 2013, Hausknecht et al., 2014, Liang et al., 2015, Lipovetzky et al., 2015, Martin et al., 2017], while others papers choose to terminate the training episodes for a subset of the games when the agent loses a life [Mnih et…”
Malthusian Reinforcement Learning (2018, background): “vations for single-agent exploration [2, 3, 9, 25, 29].”
A Meta-MDP Approach to Exploration for Lifelong Reinforcement Learning (2019, background): “not been frequently visited, [13, 22], or use approximations of a state-transition graph to exploit structural patterns, [11, 12].”
Count-Based Exploration with the Successor Representation (2018, background): “Reward bonuses that promote exploration are one alternative to random walks (e.g., Bellemare et al., 2016, Martin et al., 2017), but none such proposed solutions are widely adopted in the ﬁeld.”
Exploration in Deep Reinforcement Learning: A Survey (2022, background): “[68] BlobPROST features SARSAe Countbased Atari: Montezuma Revenge 2000 (SARSA 200) BlobPROST features Q MB D/ D”
Mega-Reward: Achieving Human-Level Play without Extrinsic Rewards (2019, methodology): “…action p(ât−1|st−1, st) before masking it by the spatial attention α(sh,wt , at−1), SoM is the softmax operation, and ᾱ(sh,wt , at−1) is the spatial attention mask before converting it into a probability distribution α(sh,wt , at−1) using the sparsemax operator (Martins and Astudillo 2016).”
Counting to Explore and Generalize in Text-based Games (2018, methodology): “To promote exploration we use an intrinsic reward by counting state visits (Kolter & Ng, 2009; Tang et al., 2017; Martin et al., 2017; Ostrovski et al., 2017).”
Improving Intrinsic Exploration with Language Abstractions (2022, background): “Exploration in RL. Exploration has a long history in RL, from " -greedy [48] or count-based exploration [4, 29, 30, 32, 47, 50] to intrinsic motivation [33–35] and curiosity-based learning [42].”
Reactive Exploration to Cope with Non-Stationarity in Lifelong Reinforcement Learning (2022, unknown): “…the exploration problem by novelty-based (Burda et al., 2019), count-based, (Strehl & Littman, 2008; Bellemare et al., 2016; Ostrovski et al., 2017; Martin et al., 2017; Tang et al., 2017; Machado et al., 2020), curiosity-based (Schmidhuber, 1991; 1990), and model-based (Stadie et al., 2015;…”
Composing Complex Skills by Learning Transition Policies (2018, methodology): “To alleviate the exploration problem with sparse rewards, our transition policy training can incorporate exploration methods such as count-based exploration bonuses (Bellemare et al., 2016; Martin et al., 2017) and curiosity-driven intrinsic reward (Pathak et al., 2017).”