  Parametric, feature-based reward models are employed by a variety of
algorithms in decision-making settings such as bandits and Markov decision
processes (MDPs). The typical assumption under which the algorithms are
analysed is realizability, i.e., that the true values of actions are perfectly
explained by some parametric model in the class. We are, however, interested in
the situation where the true values are (significantly) misspecified with
respect to the model class. For parameterized bandits, contextual bandits and
MDPs, we identify structural conditions, depending on the problem instance and
model class, under which basic algorithms such as $\epsilon$-greedy, LinUCB and
fitted Q-learning provably learn optimal policies under even highly
misspecified models. This is in contrast to existing worst-case results for,
say misspecified bandits, which show regret bounds that scale linearly with
time, and shows that there can be a nontrivially large set of bandit instances
that are robust to misspecification.
