One-shot learning and behavioral eligibility traces in sequential decision making

Marco P. Lehmann, Xu He, Vasiliki Liakoni, Michael H. Herzog, Wulfram Gerstner, Kerstin Preuschoff

TL;DR

This paper provides direct behavioral and physiological evidence that humans learn from single experiences (one-shot learning) in multi-step decision tasks, a capability attributed to "eligibility traces" in reinforcement learning models. By developing a novel experimental paradigm, the researchers demonstrate that humans can link actions taken far from a reward to that reward, a feat not possible with simpler learning models.

What Problem Does This Paper Address?

Learning to make decisions in sequences, where a reward is only received after a series of actions, is a fundamental aspect of human behavior. Think of playing chess or performing a complex motor skill. The challenge lies in the "credit assignment problem": how do we know which of the many actions taken contributed to the final outcome, especially when the reward is delayed? Reinforcement learning (RL) offers computational frameworks for this. Two main classes of RL algorithms exist: those that require many repetitions to learn (like classic temporal-difference learning) and those that can learn from a single experience (one-shot learning) using "eligibility traces." While eligibility traces are well-established in computational models and animal studies, direct human evidence for their role in one-shot sequential learning has been lacking. This paper aims to fill that gap by directly observing and measuring human behavior and physiology in a controlled sequential decision-making task.

Methods

The researchers designed a novel sequential learning task with six states and a single goal state. Participants navigated this environment by choosing between two actions in each state. Crucially, the assignment of state transitions to actions was dynamic ("on-the-fly") during the first episode, meaning participants couldn't simply memorize a fixed map. This design allowed the researchers to isolate the effects of learning from a single reward.

They then compared two hypotheses:

  1. Null Hypothesis (No Eligibility Trace): Classic RL models where reward information only propagates to the immediately preceding state-action pair. This means learning from a reward would only affect states very close to the goal after a single trial.
  2. Alternative Hypothesis (With Eligibility Trace): RL models where "eligibility traces" allow reward information to propagate to multiple preceding state-action pairs, enabling one-shot learning of longer sequences.

To directly observe the effects, they measured:

  • Behavioral Choice Probability: Participants' choices in subsequent episodes after receiving a single reward.
  • Physiological Signal (Pupil Dilation): Pupil size changes, known to correlate with cognitive variables like expected reward and prediction error.

They also conducted control experiments to rule out alternative explanations like simple memorization or novelty effects. Finally, they used computational modeling (specifically the Q-λ RL algorithm) to fit behavioral data and estimate parameters related to eligibility trace decay.

Datasets

The study utilized data collected from human participants performing the novel sequential learning task. Three different sensory modalities were used to present the states: spatial (checkerboard locations), auditory (unique sounds), and visual (clip-art images). No pre-existing datasets were used for training or evaluation; the data was generated specifically for this experiment.

Key Insights and Ideas

  • Direct Evidence for One-Shot Learning: The study provides the first direct behavioral and physiological evidence for one-shot learning of sequential actions in humans, going beyond statistical inference from multiple trials.
  • Eligibility Traces are Key: The findings strongly support the role of eligibility traces in enabling humans to learn from single experiences in complex, multi-step tasks. This is a significant step in bridging computational models of learning with human cognition.
  • Pupil Dilation as a Learning Signal: Pupil dilation was shown to reflect learned associations and reward prediction errors, serving as a valuable physiological marker for internal learning processes.
  • Cross-Modal Consistency: The observed effects were consistent across different sensory modalities (spatial, auditory, visual), suggesting the underlying learning mechanisms are modality-independent.
  • Time Scale of Learning: Computational modeling estimated the decay time of eligibility traces to be around 10 seconds, indicating that actions taken up to this duration before a reward can be effectively linked.

Key Results

  • Behavioral Bias: Participants showed a significant bias to repeat the action that led to the reward, not only in the state immediately preceding the goal (D1) but also in a state two steps away (D2). This bias was observed after only one reward experience.
  • Physiological Changes: Pupil dilation increased significantly in response to states that had been previously associated with a reward, even when those states were further away from the goal. This physiological change was observed after a single learning episode.
  • Model Performance: Reinforcement learning models with eligibility traces (specifically Q-λ, SARSA-λ, REINFORCE, and 3-step-Q) explained human behavior significantly better than models without eligibility traces (Q-0, SARSA-0).
  • Pupil Dilation and RPE: A regression analysis indicated that pupil dilation correlated more strongly with predicted reward prediction errors (RPE) than with state values, suggesting a role in signaling prediction errors.

Limitations and Future Work

  • Distinguishing RL Models: While the study strongly supports RL with eligibility traces, it acknowledges that its experimental design doesn't allow for fine-grained distinctions between all specific implementations of eligibility traces (e.g., n-step RL, prioritized sweeping).
  • Neural Implementation: The paper highlights the need for future research to identify the specific neural mechanisms underlying these eligibility traces and their role in memory and learning.
  • Time-Dependent vs. Event-Triggered Decay: The study couldn't definitively distinguish between a purely time-dependent decay of eligibility traces and an event-triggered decay. Future work could explore this by systematically varying inter-stimulus intervals.
  • Modulatory Signals: The interplay of different neuromodulators (like dopamine and norepinephrine) in mediating these learning signals remains an open question.

Summary updated

Abstract

In many daily tasks, we make multiple decisions before reaching a goal. In order to learn such sequences of decisions, a mechanism to link earlier actions to later reward is necessary. Reinforcement learning (RL) theory suggests two classes of algorithms solving this credit assignment problem: In classic temporal-difference learning, earlier actions receive reward information only after multiple repetitions of the task, whereas models with eligibility traces reinforce entire sequences of actions from a single experience (one-shot). Here, we show one-shot learning of sequences. We developed a novel paradigm to <i>directly</i> observe which actions and states along a multi-step sequence are reinforced after a single reward. By focusing our analysis on those states for which RL with and without eligibility trace make qualitatively distinct predictions, we find direct behavioral (choice probability) and physiological (pupil dilation) signatures of reinforcement learning with eligibility trace across multiple sensory modalities.
BibTeX
@inproceedings{lehmann2019one,
  author = {Marco P. Lehmann and Xu He and Vasiliki Liakoni and Michael H. Herzog and Wulfram Gerstner and Kerstin Preuschoff},
  title = {{One-shot learning and behavioral eligibility traces in sequential decision making}},
  booktitle = {eLife},
  year = {2019},
  doi = {10.7554/elife.47463},
}
Figure