We present three problems modeled after animal learning experiments designedto test online state construction or representation learning algorithms. Ourtest problems require the learning system to construct compact summaries oftheir past interaction with the world in order to predict the future, updatingonline and incrementally on each time step without an explicit training-testingsplit. The majority of recent work in Deep Reinforcement Learning focuses oneither fully observable tasks, or games where stacking a handful of recentframes is sufficient for good performance. Current benchmarks used forevaluating memory and recurrent learning make use of 3D visual environments(e.g., DeepMind Lab) which require billions of training samples, complex agentarchitectures, and cloud-scale compute. These domains are thus not well suitedfor rapid prototyping, hyper-parameter study, or extensive replication study.In this paper, we contribute a set of test problems and benchmark results tofill this gap. Our test problems are designed to be the simplest instantiationand test of learning capabilities which animals readily exhibit, including (1)trace conditioning (remembering a cue in order to predict another far in thefuture), (2) patterning (a particular combination of cues predict another), (3)and combinations of both with additional non-relevant distracting signals. Weprovide baselines for each problem including heuristics from the early days ofneural network learning and simple ideas inspired by computational models ofanimal learning. Our results highlight the difficulty of our test problems foronline recurrent learning systems and how the agent's performance oftenexhibits substantial sensitivity to the choice of key problem and agentparameters.