No-Regret with Bounded Computational Capacity

Ehud Lehrer and Eilon Solan

We deal with no regret and related aspects of vector-payoff games when one of the players is limited in computational capacity. We show that player 1 can almost approach with bounded-recall strategies, or with finite automata, any convex set which is approachable when no capacity bound is present. In particular we deduce that with bounded computational capacity player 1 can ensure having almost no regret.