A study of first-passage time minimization via Q-learning in heated gridworlds

Maria A. Larchenko, Pavel Osinenko, Grigory Yaremenko, Vladimir V. Palyulin

Introduction

In reinforcement learning (RL), environmental noise is typically treated as a uniform stochastic element or a nuisance to be filtered. However, many real-world physical systems—ranging from nanobots in turbulent fluids to financial markets—exhibit "state-dependent noise," where certain regions are inherently more volatile than others. This study explores how standard temporal-difference (TD) algorithms, such as Q-learning and SARSA, behave when navigating these "Heated Gridworlds."

The Heated Gridworld Environment

The researchers introduced the Heated Gridworld benchmark to evaluate the First-Passage Time (FPT) problem: finding the fastest path to a goal in a non-uniform stochastic environment. In this setup, specific cells are assigned a "temperature" $T$. When an agent occupies a heated cell, its intended action is perturbed by $T$ additional random steps, creating regions of high transition variance.

The Heated Gridworld environment features regions with varying levels of stochasticity (heat) and obstacles that force path selection decisions.

Stochastic Transition Dynamics

The core mechanism of the "heat" is a transition kernel that redistributes the probability of the agent's next state. In a deterministic (cold) region, an action leads directly to the adjacent cell. In a heated region, the probability mass is spread across a wider area, as shown in the kernel diagrams below. This spreading can be further complicated by boundaries, where the probability mass that would have moved "outside" the grid is reflected back, potentially creating a directional drift.

The transition kernel (a) shows the probability distribution of an agent's next state in a heated region, while (b) illustrates how boundaries reflect this noise.

The Impact of Learning Rates

The study reveals a critical interaction between the environmental noise and the agent's learning rate ($\alpha$). This interaction leads to two distinct types of biased behavior:

  • The "Fearful" Agent (High $\alpha$): With a high learning rate, agents over-index on recent negative outcomes. If a random noise "kick" pushes the agent away from the goal, the Q-value for that action is slashed. Consequently, these agents develop a strong bias toward avoiding noisy regions entirely, even if those regions offer the shortest path.
  • The "Gambler" Agent (Low $\alpha$): Conversely, low learning rates allow agents to average out noise over time. However, these agents can become biased toward heated regions. The noise acts as a passive explorer, occasionally pushing the agent toward the goal faster than its own policy would, leading the agent to overvalue high-variance transitions.

Experimental Results

Testing across 2D gridworlds and 1D intervals yielded several key findings:

  1. Path Selection Bias: In a 2D grid with an L-shaped obstacle, agents with $\alpha \approx 0.09$ chose the heated path nearly 100% of the time. When $\alpha$ was increased above 0.4, the majority of agents switched to the longer, deterministic path.
  2. Performance Degradation: Thermal noise increased the Mean First-Passage Time (MFPT) for all algorithms. High learning rates not only resulted in longer paths but also significantly higher standard deviations in performance, indicating unstable strategies.
  3. Inefficacy of Double Q-Learning: While Double Q-learning is designed to mitigate over-optimism regarding noisy rewards, it proved ineffective against the biases introduced by noisy transitions, performing similarly to standard Q-learning.

Conclusion

The research demonstrates that in environments with state-dependent noise, the choice of learning rate does more than just determine convergence speed; it fundamentally shapes the agent's preference for risk and volatility. For engineers deploying RL in physical or turbulent environments, these findings suggest a need for "noise-aware" algorithms that can distinguish between poor policy choices and inherent environmental heat.

Summary updated

BibTeX
@article{larchenko2021study,
  author = {Maria A. Larchenko and Pavel Osinenko and Grigory Yaremenko and Vladimir V. Palyulin},
  title = {{A study of first-passage time minimization via Q-learning in heated gridworlds}},
  journal = {IEEE Access},
  year = {2021},
  doi = {10.1109/access.2021.3129709},
}

Loading related content...

Figure