Per-Decision Option Discounting

Anna Harutyunyan, Peter Vrancx, Philippe Hamel, Ann Nowé, Doina PrecupICML 2019 · OpenReview

Reinforcement learning (RL) agents often struggle to reason over long time horizons. While temporal abstraction—commonly modeled through "options" (macro-actions)—allows agents to plan at a higher level, standard mathematical frameworks limit their effectiveness. This paper introduces a novel concept called "time dilation" for RL options, decoupling the discount factors used for rewards and state transitions. This approach allows agents to plan over much longer horizons without the mathematical instability typically associated with high discount factors.

The Problem: The Exponential Decay of Options

In standard RL, a discount factor ($\gamma$) tells the agent that immediate rewards are more valuable than future ones. This $\gamma$ effectively defines the agent's "horizon"—how far into the future it cares to look.

When agents use options (sequences of actions that act like a single high-level decision), the math usually dictates that an option lasting $D$ steps is discounted by $\gamma^D$. If an option takes a long time to complete (e.g., 100 steps), the signal about what happens at the end gets "washed out" by the exponential decay of the discount factor.

Value function decay over decisions

This means that even if an agent uses sophisticated high-level options, its planning horizon remains trapped by the low-level clock of the environment. Traditionally, extending this horizon requires increasing $\gamma$ toward 1.0, which makes learning incredibly slow and introduces high variance (noise).

The Solution: Per-Decision Option Discounting

To overcome this limitation, the authors propose Per-Decision Option Discounting. Instead of relying on a single $\gamma$, they introduce three distinct components:

  1. $\gamma_r$ (Reward Step-Discount): The standard discount applied to rewards accumulated within an option.
  2. $\gamma_p$ (Transition Step-Discount): A separate discount factor for the transition model. By setting $\gamma_p > \gamma_r$ (often $\gamma_p = 1$), the agent can "ignore the clock" regarding how long an option takes to complete, creating a "time dilation" effect.
  3. $\gamma_d$ (Per-Decision Discount): A state-dependent discount applied only when an option terminates. This allows the agent to reason about the number of decisions made, rather than the number of primitive steps taken.
Discount decay over timesteps showing time dilation

Crucially, the authors prove that this new framework remains a "contraction mapping." This guarantees that standard RL algorithms will still converge to a stable solution under these new rules.

Key Insights: The Variance Paradox and Horizon Invariance

This decoupled approach yields several counter-intuitive and powerful benefits:

  • The Variance Paradox: Usually, higher discounts in RL mean more noise. However, because an option's duration ($D$) is often a random variable, $\gamma^D$ is a major source of variance. By setting $\gamma_p = 1$, the randomness of the duration is entirely removed from the transition model, actually reducing variance.
  • Horizon Invariance: With time dilation, an option to "walk to the next room" can carry the same mathematical weight whether the room is 5 steps away or 50 steps away. This makes high-level policies much more robust to changes in the scale of the environment.
  • The Bias-Variance Knob: The parameters $\gamma_p$ and $\gamma_d$ act as a trade-off mechanism. While $\gamma_p=1$ reduces variance, it might introduce bias by making the agent overly optimistic about long paths. The per-decision discount $\gamma_d$ can be tuned to correct this bias.

Empirical Results

The authors evaluated their approach across several classic RL environments modified to test temporal reasoning:

  • Scale Independence (Growing Gridworld): As the distance between goals increased in a gridworld, standard agents failed because their fixed $\gamma$ made distant goals "disappear" from their horizon. The time-dilated agent maintained perfect performance regardless of the grid size.
  • Faster Discovery (Chain Task): In a linear environment with noisy distractor rewards, agents using time dilation discovered the optimal long-term strategy significantly faster than standard agents.
  • Theoretical Alignment (Four Rooms): Empirical results in a standard Four Rooms domain closely matched the novel bias-variance bounds derived in the paper, confirming that the variance reduction is a real, exploitable property.

Limitations and Future Directions

While powerful, moving from one discount factor to three adds parameter complexity. The paper provides theoretical tools to understand their impact but does not offer a universal rule for picking the "best" values.

Future research directions include automatically learning these discount parameters based on the specific options being used. Additionally, this framework shows immense promise for transfer learning—allowing an agent to learn a policy on a small version of a task and transfer the "time-dilated" model to a much larger, scaled-up version of the same environment.

Summary updated

Abstract

In order to solve complex problems an agent must be able to reason over a sufficiently long horizon. Temporal abstraction, commonly modeled through options, offers the ability to reason at many tim...
BibTeX
@inproceedings{harutyunyan2019per,
  author = {Anna Harutyunyan and Peter Vrancx and Philippe Hamel and Ann Nowé and Doina Precup},
  title = {{Per-Decision Option Discounting}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=Syb-uhWO-H},
}

Loading related content...

Figure