or unsuited to the task (see Section \[sec:treemaze\]).

![Observations of the Khepera robot. a) Color image from the camera. b) Color blobs detected by the vision system, as observed by the robot. QR-codes can only be decoded when the robot is a couple of inches away from them.[]{data-label="fig:khepera_observations"}](figures/khepera_observations)

Background
==========

This section formally introduces Markov Decision Processes (MDPs), Options, Partially Observable MDPs (POMDPs) and Finite State Controllers, before presenting our main contribution in Section \[sec:ooi\].

Markov Decision Processes
-------------------------

A discrete-time Markov Decision Process (MDP) $\langle S, A, R, T, \gamma \rangle$ with discrete actions is defined by a possibly-infinite set $S$ of states, a finite set $A$ of actions, a reward function $R(s_t, a_t, s_{t+1}) \in \mathcal{R}$, that provides a scalar reward $r_t$ for each state transition, a transition function $T(s_t, a_t, s_{t+1}) \in [0, 1]$, that outputs a probability distribution over new states $s_{t+1}$ given a $(s_t, a_t)$ state-action pair, and $0 \le \gamma < 1$ the discount factor, that defines how sensitive the agent should be to future rewards.

A stochastic memoryless policy $\pi(s_t, a_t) \in [0, 1]$ maps a state to a probability distribution over actions. The goal of the agent is to find a policy 