When the Best Move Isn't Optimal: Q-learning with Exploration

George H. JohnAAAI 1994

Abstract

Standard Q-learning assumes an agent will always follow the "optimal" path, but in reality, agents must explore—often by taking random actions. This paper introduces $\hat{Q}$-learning, which incorporates the agent's exploration strategy directly into its value updates, resulting in "safer" policies that achieve higher average rewards in unpredictable environments. By replacing the standard maximum operator with an expected value operator, the agent becomes "self-aware" of its own exploration-driven errors, favoring paths where mistakes are less costly.

Introduction

In Reinforcement Learning (RL), the goal is typically to find an optimal policy that maximizes future rewards. Standard Q-learning (Watkins, 1989) calculates these rewards under the assumption that the agent will always pick the best possible move in the future. However, to learn about the world or adapt to changes, agents must explore, which involves taking suboptimal or random actions.

If an agent is destined to keep exploring, the "optimal" path found by standard Q-learning might be dangerous. For example, a path along a narrow cliff edge is optimal if you never slip, but if you have a 10% chance of taking a random step, that path becomes a liability. This paper addresses the gap between theoretical optimality and the practical reality of persistent exploration.

Methods

The author proposes a modification to the standard Q-learning update rule to account for behavioral constraints.

Standard Q-learning

When updating the value of a state, standard Q-learning uses the maximum expected future reward: $$\hat{V}(x) \leftarrow \max_a \hat{Q}(x, a)$$

$\hat{Q}$-learning

The proposed $\hat{Q}$-learning replaces the "max" operator with an expected value operator that accounts for the probability $P(a)$ of taking any given action $a$ (including exploratory ones): $$\hat{V}(x) \leftarrow \sum_a P(a) \hat{Q}(x, a)$$

By using the expected reward rather than the maximum reward, the agent learns a policy robust to its own tendency to wander. If the exploration strategy $P(a)$ is unknown, it can be estimated using sample statistics during the learning process.

Experimental Setup

The algorithm was evaluated using a custom Grid World simulation. The environment consists of a grid where an agent starts in the center (S). To the left is a "wall" of goal states (G); to the right is a single goal state (G). All goals provide a reward of 9 units.

The simulation ran for $10^6$ steps with a discount rate ($\gamma$) of 0.9 and a learning rate ($\beta$) of 0.5. A "random walk" exploration strategy was used, where the agent took a random action instead of the recommended one 30% of the time.

Results and Analysis

The core "aha moment" of this research is that an agent should be "self-aware" of its own exploration policy. By knowing it might make a mistake, it chooses paths where mistakes are less costly.

In the grid world example, both the "wall of goals" (left) and the "single goal" (right) are two steps away. Standard Q-learning treats these as equal because it assumes perfect execution in the future.

Figure 1: Policy generated by standard Q-learning, showing indifference between the left and right goal paths.

However, $\hat{Q}$-learning prefers the left. If the agent "slips" (explores) and moves up or down while heading left, it is still near a goal. If it slips while heading toward the single goal on the right, it misses entirely.

Figure 2: Policy generated by $\hat{Q}$-learning, which correctly identifies the left path as safer due to the 'wall of goals' providing a margin for error during exploration.

In the experiment, standard Q-learning achieved an average reward of 3.35, while $\hat{Q}$-learning achieved 3.44. The improvement is consistent across experiments, though the degree depends on the domain and exploration rate. Notably, when exploration is turned off, the two algorithms become mathematically equivalent.

Discussion

While $\hat{Q}$-learning offers a more realistic approach to value updates, it introduces new challenges. Calculating the sum $\sum_a P(a) \hat{Q}(x, a)$ may be computationally expensive in complex environments with sophisticated exploration strategies like Boltzmann exploration. Furthermore, the current study is limited to simple grid worlds; future work should explore how this approach scales to high-dimensional state spaces or continuous control problems, and how it handles dynamic exploration strategies that change over time.

Summary updated

BibTeX
@inproceedings{john1994when,
  author = {George H. John},
  title = {{When the Best Move Isn't Optimal: Q-learning with Exploration}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure