PaperlayerView exact revision on arXiv

Source-linked AI summary

Count-Based Exploration in Feature Space for Reinforcement Learning

Jarryd Martin, Suraj Narayanan Sasikumar, Tom Everitt, Marcus Hutter

arXiv:1706.08090v1cs.AI

TL;DR

In large state-action spaces, value approximation can generalize across unvisited states, but few methods generalize uncertainty for efficient exploration. This paper uses value-function features to derive generalized visit-counts and exploration bonuses. Its evaluation reports improvements over ϵ-greedy exploration across games and competitiveness with leading deep-RL exploration methods.

  • Problem

    In large state-action spaces, most states are unvisited, and few methods generalize uncertainty to support efficient exploration.

    Source: §1 · p. 1

  • Method

    The φ-Exploration Bonus derives generalized visit-counts from feature-space density using features already used for value approximation.

    Source: §1 · p. 1, §3 · p. 3, §3.1 · p. 3

  • Results

    The evaluation reports improvement over ϵ-greedy exploration on a variety of games and competitiveness with leading deep-RL exploration techniques.

    Source: §6 · p. 6

  • Takeaways & Limitations

    The method uses value-function features rather than a separate exploration-specific representation and is simpler and less computationally demanding than some other proposals.

    Source: §1 · p. 2, §6 · p. 6

    The method relies on the feature representation used for LFA, and its combination with nonlinear function approximation is unclear.

    Source: §6 · p. 7

Abstract

from arXiv · show

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.

1 Introduction

Large state-action spaces make generalization from limited experience essential, yet efficient exploration remains difficult because conventional visit-counts stay at zero for most unvisited states. The paper estimates uncertainty using features already used for value approximation, yielding a simpler, less computationally expensive exploration method with near state-of-the-art benchmark performance.

1 Introduction

  • Conventional count-based exploration is ineffective in high-dimensional spaces because most states are never visited and retain zero counts.Efficient exploration remains comparatively underdeveloped even in methods using nonlinear value estimation.Source: §1 · p. 1
  • The method computes generalized visit-counts from a density model over the feature representation used for value approximation.States with frequently observed features receive higher counts, while bonuses encourage exploration of regions with less familiar features.Source: §1 · pp. 1–2
  • The method uses the same lower-dimensional features to estimate value and uncertainty, avoiding a separate exploration-specific state representation.The density model can be derived from an LFA feature map with little or no additional design.Source: §1 · p. 2
  • The evaluation reports near state-of-the-art performance on high-dimensional RL benchmarks.The approach is also described as simpler and less computationally expensive than some existing proposals.Source: §1 · p. 2

2 Background and Related Work

RL agents must generalize value estimates and balance exploration with exploitation, but tabular optimism and visit-counts scale poorly when the state space is large. Prior large-domain methods address this with generalized counts derived from density models or state clustering.

2.1 Reinforcement Learning

  • Function approximation generalizes value estimates, whereas tabular value representations lack structure for generalizing across similar states.In linear function approximation, the approximate action-value function is a linear combination of state-action features.Source: §2.1 · p. 2

2.2 Count-Based Exploration and Optimism

  • Exploration gathers information to reduce uncertainty, while exploitation uses current information to maximize expected cumulative reward.Optimism-based count methods add larger bonuses to less-visited state-action pairs.Source: §2.2 · p. 2

2.3 Exploration in Large MDPs

  • Tabular optimism performs well on small MDPs but has prohibitive sample complexity for larger problems, and its bound offers no performance guarantee when high-dimensional states cannot all be visited.Large-domain alternatives use generalized counts from density models or locality-sensitive hashing; these methods outperform random strategies in hard large discrete domains.Source: §2.3 · pp. 2–3

3 Method

The method estimates novelty using features already used for value approximation, avoiding pairwise comparisons with the full history. It turns feature-space densities into generalized counts and exploration bonuses, with computation scaling in the number of features.

3 Method

  • φ-EB measures novelty using the feature representation for value approximation, treating states as similar when they share features relevant to value.This avoids a separate exploration-specific representation and motivates feature-space novelty as a simpler, more principled approach.Source: §3 · p. 3

3.1 A Visit-Density over Feature Space

  • The feature visit-density assigns higher probability to states sharing features with frequently observed states, and lower probability when they contain more novel features.It models feature factors independently with count-based estimators, allowing novelty estimates to be learned from little data.Source: §3.1 · p. 3

3.2 The φ-pseudocount

  • The method derives naive and standard φ-pseudocounts from the feature visit-density.The density model provides the basis for both generalized-count variants.Source: §3.2 · p. 3

3.3 Reinforcement Learning with φ-EB

  • φ-EB computes an exploration bonus from the φ-pseudocount, adds it to the reward, and trains a value-based LFA algorithm on the augmented reward.Each timestep updates at most one estimator per feature; computation scales with the number of features, or observed features when sparse vectors use a shared prototype estimator.Source: §3.3 · p. 4

4 Theoretical Results

The theoretical results relate binary-feature Hamming similarity to feature visit-density and the φ-pseudocount: states sharing few features with history receive low density and low pseudocount. Minimizing the pseudocount also minimizes a lower bound on similarity without directly computing feature distances.

4 Theoretical Results

  • The proof analyzes binary features and the naive φ-exploration bonus; analogous results for the empirical pseudocount are expected, not proved here.The implementation uses an empirical estimator for factor models in the visit-density.Source: §4 · p. 4
  • Few-feature overlap with history yields low feature-visit density and therefore a low φ-pseudocount.The theorem and corollary connect Hamming similarity to both quantities.Source: §4 · pp. 4–5
  • Choosing the state with minimum φ-pseudocount also minimizes a lower bound on Hamming similarity, without directly computing feature distances.The pseudocount thus acts as a feature-space novelty measure.Source: §4 · p. 5

5 Empirical Evaluation

The evaluation tests feature-derived novelty across sparse- and dense-reward ALE games, compares φ-EB with ϵ-greedy and leading exploration methods, and examines whether it competes with deep RL.

5 Empirical Evaluation

  • The experiments ask whether LFA-derived novelty generalises visit-counts, improves across reward types, and competes with exploration methods and deep RL.The comparison includes count-based methods and a model-prediction-error exploration method.Source: §5 · p. 5, Comparison with Leading Algorithms · p. 6

5.1 Setup

  • The evaluation uses five ALE games with sparse or dense rewards, training agents for 100 million frames except Q*bert at 80 million, then scoring 500 episodes.Montezuma’s Revenge and Venture received five independent trials each; the other games received two.Source: §5.1 · p. 5

Comparison with ϵ-greedy Baseline

  • In Freeway, β = 0.05 underperformed Sarsa-ϵ, while β = 0.035 performed better.The authors suggest sensitivity may reflect many active Blob-PROST features that are irrelevant to the optimal policy.Source: Comparison with ϵ-greedy Baseline · p. 6
  • With β = 0.05, Sarsa-φ-EB outperformed Sarsa-ϵ on every tested game except Freeway.On Montezuma, Sarsa-ϵ rarely left the first room while Sarsa-φ-EB visited up to 14 rooms; on Venture, Sarsa-ϵ failed to score.Source: Comparison with ϵ-greedy Baseline · pp. 5–6

Comparison with Leading Algorithms

  • Sarsa-φ-EB scored 2745.4 on Montezuma, the second-highest reported score, and achieved state-of-the-art performance on Venture.It was also competitive in Frostbite, while nonlinear algorithms performed better in Q*bert and Sarsa-φ-EB failed to score in Freeway.Source: Comparison with Leading Algorithms · p. 6

6 Conclusion

The conclusion presents φ-Exploration Bonus as a scalable, simpler count-based exploration method that improves on ϵ-greedy across varied games and competes with leading deep-RL exploration methods, while noting its reliance on LFA features.

6 Conclusion

  • φ-Exploration Bonus scales to high-dimensional environments, improves on ϵ-greedy across a variety of games, and is competitive with leading deep-RL exploration techniques.It uses the approximate value function’s features rather than requiring an exploration-specific state representation, and is described as simpler and less computationally demanding than some proposals.Source: §6 · p. 6
  • Table 1 reports average evaluation scores with training budgets ranging from 20M to 200M frames.Sarsa-φ-EB and Sarsa-ϵ used 100M frames except on Q*bert, where they used 80M.Source: Table 1 · p. 7
  • The method relies on the LFA feature representation, and its combination with nonlinear function approximation remains unclear.The authors identify this as a limitation and hope the method’s success inspires future work in that direction.Source: §6 · p. 7

Related papers

Loading 1706.08090v1…