One-shot learning and eligibility traces in sequential decision making

When humans or animals perform an action that led to a desired outcome, they show a tendency to repeat it. The mechanisms underlying learning from past experience and adapting future behavior are still not fully understood. In this thesis, I study how humans learn from sparse and delayed reward during multi-step tasks. Learning a sequence of multiple decisions, from a reward obtained only at the end of the sequence, requires a mechanism to link earlier actions to later reward. The theory of reinforce- ment learning suggests an algorithmic solution to this problem, namely, to keep a decaying memory of the state-action history. Such memories are called eligibility traces. They bridge the temporal delay between the moment an action is taken and a subsequent reward. We ask whether humans make use of eligibility traces when learning a sequential decision making task. The difficulty in answering this question is that different competing algorithmic solu- tions make similar predictions about behavior. Only during a few initial trials, learning with eligibility traces is qualitatively different from other algorithms. Here, I implemented a novel learning task with an experimental manipulation that allowed us to guide participants through a controlled sequence of states. With this hidden manipulation, we were able to isolate the specific trials in which the competing models are distinguishable. Behavioral data as well as simultaneously recorded pupil dilation revealed effects compatible with eligibility traces, but not with simpler models. Furthermore, the trial-by-trial reward prediction errors were correlated with pupil dilation and EEG measurements. Our experimental data show effects of eligibility traces in behavior and pupil data, after a single experience of state-action associations, which has not been studied before in a multi-step task. We view our results in the light of one-shot learning and as a signature of a learning mechanism present both in temporal difference and one-shot learning.

Evidence for eligibility traces in human learning

Wulfram Gerstner, Michael Herzog, Marco Philipp Lehmann, Vasiliki Liakoni, Kerstin Preuschoff, He Xu

Whether we prepare a coffee or navigate to a shop: in many tasks we make multiple decisions before reaching a goal. Learning such state-action sequences from sparse reward raises the problem of credit-assignment: which actions out of a long sequence should be reinforced? One solution provided by reinforcement learning (RL) theory is the eligibility trace (ET); a decaying memory of the state-action history. Here we investigate behaviorally and neurally whether humans utilize an ET when learning a multi-step decision making task. We implemented three versions of a novel task using visual, acoustic, and spatial cues. Eleven subjects performed all three conditions while we recorded their pupil diameter. We considered model-based and model-free (with and without ET) algorithms to explain human learning. Using the Akaike Information Criterion (AIC) we find that model-free learning with ET explains the human behavior best in all three conditions. Cross-validation confirms this behavioral result. We then compare pupil dilation in early and late learning and observe differences that are consistent with an ET contribution. In particular, we find significant changes in pupil response to non-goal states after just a single reward in all three experimental conditions. In this research we introduce a novel paradigm to study the ET in human learning in a multi-step sequential decision making task. The analysis of the behavioral and pupil data provides evidence that humans utilize an eligibility trace to solve the credit-assignment problem when learning from sparse and delayed reward.

arXiv2017

Surprise-based model estimation in reinforcement learning: algorithms and brain signatures

Vasiliki Liakoni

Learning how to act and adapting to unexpected changes are remarkable capabilities of humans and other animals. In the absence of a direct recipe to follow in life, behaviour is often guided by rewarding and by surprising events. A positive or a negative outcome influences the tendency to repeat some actions, and a sudden unexpected event signals the possible need to act differently or to update one's view about the world. Advances in computational, behavioral, and cognitive neuroscience have indicated that animals employ multiple strategies to learn from interaction. However, our understanding of learning strategies and how they are combined is largely restricted. The main goal of this thesis is to study the use of surprise by ever-adapting biological agents, its contributions to reward-based learning, and its manifestation in the human brain. We first study surprise from a theoretical perspective. In a probabilistic model of changing environments, we show that exact and approximate Bayesian inference give rise to a trade-off between forgetting old observations and integrating them with new ones, modulated by a naturally emerging surprise measure. We develop novel surprised-based algorithms that can adapt in the face of abrupt changes and accurately estimate the model of the world, and that could potentially be implemented in the brain. Next, we focus on the contributions of surprise-based model estimation to reinforcement learning. We couple one of our adaptive algorithms as well as simpler non-adaptive methods with reinforcement learning agents and evaluate their performance on environments exhibiting different characteristics. Abrupt changes that directly affect the agent's policy call for surprise-based adaptation, in order to achieve higher performance. Often, however, the agent does not need to invest in maintaining an accurate model of the environment to obtain high reward levels. More specifically, in stochastic environments or in environments with distal changes, simpler methods, equipped with exploration capacity, perform equally well compared to more elaborate methods. Finally, we turn to human learning behaviour and brain signals of surprise- and reward-based learning. We design a novel sequential decision making task of multiple steps where strategic use of surprising events allows us to dissociate fMRI brain correlates of reward learning and model estimation. We show that Bayesian inference on this task leads to the same surprise measure we found earlier, where the trade-off is now between ignoring new observations and integrating them with the old belief, and we develop reinforcement learning algorithms that perform outlier detection via this surprise-modulated trade-off. At the level of behaviour we find evidence for a model-free policy learning architecture, with potential influences from a model estimation system. At the level of brain responses we identify signatures of both reward- and model estimation signals, supporting the existence of multiple parallel learning systems in the brain. This thesis presents a comparative analysis of surprise-based model estimation methods in theory and simulations, provides insights in the type of approximations that biological agents may adopt, and identifies signatures of model estimation in the human brain. Our results may aid future work aiming at building efficient adaptive agents and at understanding the learning algorithms and the surprise measures implemented in the brain.

EPFL2021

Understanding Deep Neural Function Approximation in Reinforcement Learning via ϵ-Greedy Exploration

Volkan Cevher, Luca Viano

This paper provides a theoretical study of deep neural function approximation in reinforcement learning (RL) with the ϵ-greedy exploration under the online setting. This problem setting is motivated by the successful deep Q-networks (DQN) framework that falls in this regime. In this work, we provide an initial attempt on theoretical understanding deep RL from the perspective of function class and neural networks architectures (e.g., width and depth) beyond the ``linear'' regime. To be specific, we focus on the value based algorithm with the ϵ-greedy exploration via deep (and two-layer) neural networks endowed by Besov (and Barron) function spaces, respectively, which aims at approximating an α-smooth Q-function in a d-dimensional feature space. We prove that, with T episodes, scaling the width

m = \widetilde{\mathcal{O}}(T^{\frac{d}{2\alpha + d}})

and the depth

L=\mathcal{O}(\log T)

of the neural network for deep RL is sufficient for learning with sublinear regret in Besov spaces. Moreover, for a two layer neural network endowed by the Barron space, scaling the width

\Omega(\sqrt{T})

is sufficient. To achieve this, the key issue in our analysis is how to estimate the temporal difference error under deep neural function approximation as the ϵ-greedy exploration is not enough to ensure "optimism". Our analysis reformulates the temporal difference error in an

L^2(\mathrm{d}\mu)

-integrable space over a certain averaged measure μ, and transforms it to a generalization problem under the non-iid setting. This might have its own interest in RL theory for better understanding

\epsilon

-greedy exploration in deep RL.

2022