  This paper looks at predictability problems, i.e., wherein an agent must
choose its strategy in order to optimize the predictions that an external
observer could make. We address these problems while taking into account
uncertainties on the environment dynamics and on the observed agent's policy.
To that end, we assume that the observer 1. seeks to predict the agent's future
action or state at each time step, and 2. models the agent using a stochastic
policy computed from a known underlying problem, and we leverage on the
framework of observer-aware Markov decision processes (OAMDPs). We propose
action and state predictability performance criteria through reward functions
built on the observer's belief about the agent policy; show that these induced
predictable OAMDPs can be represented by goal-oriented or discounted MDPs; and
analyze the properties of the proposed reward functions both theoretically and
empirically on two types of grid-world problems.
