Reannealing of Decaying Exploration Based On Heuristic Measure in Deep Q-Network

Xing Wang, Alexander Vinel

Abstract

Existing exploration strategies in reinforcement learning (RL) often either ignore the history or feedback of search, or are complicated to implement. There is also a very limited literature showing their effectiveness over diverse domains. We propose an algorithm based on the idea of reannealing, that aims at encouraging exploration only when it is needed, for example, when the algorithm detects that the agent is stuck in a local optimum. The approach is simple to implement. We perform an illustrative case study showing that it has potential to both accelerate training and obtain a better policy.

1. Introduction

In Reinforcement Learning (RL), agents face a fundamental "exploration-exploitation" dilemma. The standard approach is $\epsilon$-greedy decay, where the agent starts by acting randomly and gradually becomes more "greedy" over time. However, if exploration decays too quickly, the agent often gets stuck in a "comfort zone"—a local optimum where it performs adequately but never discovers the truly optimal strategy. For example, in flight simulators, an agent might learn to hover safely forever to avoid crashing, but it never learns to actually land because it stops exploring before it finds the landing pad. This paper introduces "Exploration Reannealing," a simple yet effective technique to prevent Deep Q-Network (DQN) agents from getting stuck in such local optima.

2. Methods: Exploration Reannealing

The proposed method is inspired by Simulated Annealing, a classic optimization technique. The approach works as follows:

  1. Standard DQN/DDQN: The base is a standard Double Deep Q-Network (DDQN) using $\epsilon$-greedy exploration.
  2. Heuristic Monitoring: Instead of relying solely on rewards, which can be noisy or ambiguous, the algorithm uses a separate, domain-specific heuristic measure to detect if the agent is stuck.
  3. The Reanneal Trigger: If the heuristic detects a bottleneck (e.g., the agent has spent too many episodes failing to reach a terminal state), the exploration rate $\epsilon$ is "reannealed"—reset to 1 (pure exploration).
  4. Redecay: After the reset, $\epsilon$ begins to decay again, forcing the agent to use its newfound random experiences to break out of its local optimum.

This approach is model-free and off-policy, meaning the agent can learn from the high-entropy data gathered during the reannealing phase without destabilizing its underlying target policy.

3. Experimental Setup

The researchers evaluated their method using the Lunar Lander environment from OpenAI Gym (Box2D).

The Lunar Lander environment, where the agent must land between two yellow flags.
  • State Space: An 8-dimensional vector (coordinates, velocities, angles, and ground contact indicators).
  • Action Space: 4 discrete actions (do nothing, fire left engine, fire main engine, fire right engine).
  • The Challenge: The agent must land between two flags at zero speed. Crashing is penalized (-100), while successful landing is rewarded (+100 to +140).

4. Key Results and Insights

The results demonstrate a clear advantage for reannealing across several metrics:

  • Higher Performance: Agents with reannealing reached average episodic rewards of ~200 (indicating smooth, accurate landings). Without reannealing, agents often plateaued at much lower scores or failed to reach the landing pad consistently.
  • Faster Convergence: To reach a success threshold (reward > 100), the reannealing agent took fewer than 4,000 episodes, whereas the standard agent required over 7,000 episodes (using a decay rate of 0.985).
  • Sample Efficiency: When an agent is stuck, its Temporal Difference (TD) errors are usually small. Reannealing pushes the agent into unacquainted states with high TD errors, which are much richer sources of information for the neural network.
  • Stability: Once the reannealing agent broke out of the "hovering" local optimum, the variance in its performance decreased, leading to a more robust final policy.

5. Conclusion and Future Work

Exploration reannealing acts as a safety net for hyperparameters. Even if the initial decay is too aggressive, the reannealing trigger eventually forces the agent back into an exploration phase to "fix" its policy. The primary limitation is that the heuristic measure is currently hand-engineered for the specific task (e.g., counting timeouts while hovering). Future work could involve training a supervised model to automatically learn these heuristic triggers from experience, potentially creating a fully automated, domain-agnostic reannealing framework.

Summary updated

Abstract

Existing exploration strategies in reinforcement learning (RL) often either ignore the history or feedback of search, or are complicated to implement. There is also a very limited literature showing their effectiveness over diverse domains. We propose an algorithm based on the idea of reannealing, that aims at encouraging exploration only when it is needed, for example, when the algorithm detects that the agent is stuck in a local optimum. The approach is simple to implement. We perform an illustrative case study showing that it has potential to both accelerate training and obtain a better policy.
BibTeX
@misc{wang2020reannealing,
  author = {Xing Wang and Alexander Vinel},
  title = {{Reannealing of Decaying Exploration Based On Heuristic Measure in Deep Q-Network}},
  year = {2020},
  eprint = {2009.14297},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2009.14297},
}
Figure