Better-Reply Dynamics with Bounded Recall

A decision maker is engaged in a repeated interaction with Nature. The objective of the decision maker is to guarantee to himself the average payoff as large as the best–reply payoff to Nature's empirical distribution of play, no matter what Nature does. The decision maker with perfect recall can achieve this objective by a simple better–reply strategy. In this paper we demonstrate that the relationship between perfect recall and bounded recall is not straightforward: The decision maker with bounded recall may fail to achieve this objective, no matter how long his recall and no matter what better–reply strategy he uses.