Learning State Features from Policies to Bias Exploration in Reinforcement Learning

Bryan Singer, Manuela M. VelosoAAAI 1999 · OpenReview

Abstract

When given several problems to solve in some domain, a standard reinforcement learner learns an optimal policy from scratch for each problem. If the domain has particular characteristics that are goal and problem independent, the learner might be able to take advantage of previously solved problems. Unfortunately, it is generally infeasible to directly apply a learned policy to new problems. This paper presents a method to bias exploration through previous problem solutions, which is shown to speed up learning on new problems. We first allow a Q-learner to learn the optimal policies for several problems. We describe each state in terms of local features, assuming that these state features together with the learned policies can be used to abstract out the domain characteristics from the specific layout of states and rewards in a particular problem. We then use a classifier to learn this abstraction by using training examples extracted from each learned Q-table. The trained classifier maps state features to the potentially goal independent successful actions in the domain. Given a new problem, we include the output of the classifier as an exploration bias to improve the rate of convergence of the reinforcement learner. We have validated our approach empirically in the complex domain of Sokoban.

Introduction

Standard Reinforcement Learning (RL) agents typically treat every new task as an independent learning problem, even when tasks share structural similarities within the same domain. This "forgetfulness" leads to significant computational overhead as agents relearn basic domain principles (e.g., avoiding dead ends) from scratch. The authors propose a method to extract general "domain wisdom" from simple tasks and apply it as an exploration bias to accelerate learning in more complex, novel environments.

Methodology

The proposed approach utilizes a four-stage pipeline to transfer knowledge:

  1. Base Learning: A standard Q-learner solves a set of simple training problems to generate optimal Q-tables.
  2. Feature Extraction & Labeling: States from the Q-tables are converted into local state features (e.g., the immediate surroundings of the agent). Actions are labeled as positive if they have maximum Q-values and negative if they never lead to a goal.
  3. Supervised Learning: A neural network (NN) classifier is trained to map these local features to successful actions, effectively turning agent experience into a general-purpose heuristic.
  4. Biased Exploration: In new problems, the agent uses the NN's predictions to bias its exploration. Unlike a standard $\epsilon$-greedy approach that explores randomly, this agent prioritizes actions that "look" successful based on prior domain experience.

Experimental Evaluation

The method was evaluated in the Sokoban domain, a grid-based puzzle requiring strategic movement to push objects to targets. The primary metric was the average number of steps required to reach the goal across training epochs.

Comparison of learning rates for biased (with NN) and unbiased (without NN) agents in the Sokoban domain.

As shown in the figure above, the biased learner ("with NN") demonstrates a significant advantage from the outset. While both agents may start with high step counts, the biased learner converges to a near-optimal performance of approximately 18 steps almost immediately. In contrast, the unbiased learner ("without NN") remains at a much higher step count (averaging 20-21 steps) for the first 35 epochs, only reaching the biased agent's performance level after approximately 50 epochs of training. This demonstrates that the neural network successfully captured domain-specific heuristics that generalized to new puzzle layouts.

Conclusion

By shifting from global state IDs to local features and using supervised learning to capture successful action patterns, the authors provide a robust mechanism for knowledge transfer in RL. The use of the classifier as an exploration bias, rather than a fixed policy, ensures that the agent can still converge to an optimal solution even if the heuristic is imperfect. Future work may explore automated feature discovery and scaling to continuous state spaces.

Summary updated

Abstract

When given several problems to solve in some domain, a standard reinforcement learner learns an optimal policy from scratch for each problem. If the domain has particular characteristics that are goal and problem independent, the learner might be able to take advantage of previously solved problems. Unfortunately, it is generally infeasible to directly apply a learned policy to new problems. This paper presents a method to bias exploration through previous problem solutions, which is shown to speed up learning on new problems. We first allow a Q-learner to learn the optimal policies for several problems. We describe each state in terms of local features, assuming that these state features together with the learned policies can be used to abstract out the domain characteristics from the specific layout of states and rewards in a particular problem. We then use a classifier to learn this abstraction by using training examples extracted from each learned Q-table. The trained classifier maps state features to the potentially goal independent successful actions in the domain. Given a new problem, we include the output of the classifier as an exploration bias to improve the rate of convergence of the reinforcement learner. We have validated our approach empirically. In this paper, we report results within the complex domain Sokoban which we introduce.
BibTeX
@inproceedings{singer1999learning,
  author = {Bryan Singer and Manuela M. Veloso},
  title = {{Learning State Features from Policies to Bias Exploration in Reinforcement Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
  url = {https://openreview.net/forum?id=Hk-B5lZOWr},
}
Figure