Reinforcement with Fading Memories

Kuang Xu, Se-Young Yun

TL;DR

This paper investigates how imperfect memory affects decision-making in a reinforcement learning setting. The authors introduce a model where past rewards decay over time and derive analytical results showing that the agent's performance hinges on the balance between how quickly it updates its choices and how fast its memory fades.

What Problem Does This Paper Address?

In real-world scenarios, decision-makers rarely have perfect recall of past experiences. Memories fade, and the ability to adapt to new information is crucial for optimal decision-making. This paper addresses the question of how imperfect memory impacts an agent's ability to make good choices in a dynamic environment where actions yield rewards at different rates. Specifically, it explores the trade-off between the rate at which past rewards are forgotten (memory decay) and the rate at which the agent updates its strategy based on current information.

Methods

The authors model the problem as a stochastic sequential action-reward process. An agent chooses actions, receives rewards, and these rewards decay in memory at a rate $\mu$. The agent can also update its choices at a rate $\beta$. The core of their approach is analyzing a specific decision rule: the "reward matching rule," where the probability of choosing an action is proportional to the accumulated, non-decayed rewards associated with it.

A key methodological contribution is the analysis in the "memory-abundant regime" where the memory decay rate $\mu$ approaches zero. This regime is analyzed using fluid approximations, which allow for deriving closed-form solutions for the agent's steady-state behavior. The authors also distinguish between a "memory-abundant" ($\beta \gg \mu$) and a "memory-deficient" ($\beta \ll \mu$) regime, each exhibiting distinct dynamics.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Memory matters, but balance is key: The agent's success is not solely determined by having a long memory, but by the interplay between memory decay and decision update rates.
  • "Winner-takes-all" in memory-abundant regimes: When the agent updates its choices much faster than its memory decays, and with a small exploration parameter, it tends to focus almost exclusively on the best action, mirroring optimal behavior.
  • "Reward-rate-proportional" in memory-deficient regimes: When memory decays faster than choices are updated, the agent's choices become more spread out, with probabilities roughly proportional to the reward rates of the actions.
  • "Complete oblivion" with rapid updates: Counter-intuitively, if the agent updates its choices too frequently and has a high exploration parameter, it can lead to a state where it chooses actions almost randomly, failing to learn effectively.

Key Results

The paper provides closed-form formulas for the steady-state choice distribution of the agent.

  • Memory-abundant regime ($\beta \gg \mu$):
    • If the exploration parameter $\alpha_0$ is small relative to the best reward rate ($\alpha_0 \le \lambda_1/K$), the agent almost always chooses the best action (probability close to 1).
  • If $\alpha_0$ is large ($\alpha_0 > \lambda_1/K$), the agent chooses actions uniformly at random.
  • Memory-deficient regime ($\beta \ll \mu$):
    • The agent's choice probabilities are approximately proportional to $\lambda_k \vee \alpha_0 + (K-1)\alpha_0$, where $\lambda_k$ is the reward rate of action $k$, $\alpha_0$ is the exploration parameter, and $K$ is the number of actions. This means choices are biased towards actions with higher reward rates, but not to the extreme "winner-takes-all" extent seen in the other regime.

Limitations and Future Work

The authors acknowledge that their analysis primarily focuses on the memory-abundant regime ($\mu \to 0$) and the reward matching rule. They suggest several avenues for future work:

  • Exploring other lifespan distributions: The current model assumes exponential lifespans for rewards. Investigating other distributions (e.g., heavy-tailed) could reveal different dynamics.
  • Generalizing choice models: Extending the analysis beyond the reward matching rule to more general choice heuristics (e.g., polynomial or exponential weighting of rewards) is a promising direction.
  • Analyzing the $\beta = \Theta(\mu)$ regime: This intermediate regime, where update and decay rates are comparable, is mathematically challenging and left open.
  • Investigating non-stationary environments: The current model assumes fixed reward rates. Extending it to handle time-varying reward rates would be more realistic.
  • Understanding the impact of "artificial" memory loss: Exploring whether intentionally inducing memory loss could be beneficial in certain scenarios.

Summary updated

Abstract

We study the effect of imperfect memory on decision making in the context of a stochastic sequential action-reward problem. An agent chooses a sequence of actions which generate discrete rewards at different rates. She is allowed to make new choices at rate $\beta$, while past rewards disappear from her memory at rate $\mu$. We focus on a family of decision rules where the agent makes a new choice by randomly selecting an action with a probability approximately proportional to the amount of past rewards associated with each action in her memory. We provide closed-form formulae for the agent's steady-state choice distribution in the regime where the memory span is large ($\mu \to 0$), and show that the agent's success critically depends on how quickly she updates her choices relative to the speed of memory decay. If $\beta \gg \mu$, the agent almost always chooses the best action, i.e., the one with the highest reward rate. Conversely, if $\beta \ll \mu$, the agent chooses an action with a probability roughly proportional to its reward rate.
BibTeX
@inproceedings{xu2018reinforcement,
  author = {Kuang Xu and Se-Young Yun},
  title = {{Reinforcement with Fading Memories}},
  booktitle = {SIGMETRICS (Abstracts)},
  year = {2018},
  doi = {10.1145/3219617.3219653},
}
Figure