Globally optimal strategy against the Hedge algorithm in repeated games

This paper studies the algorithm exploitation problem and aims to solve the optimal strategy against a well-known adaptive algorithm, the Hedge algorithm, in finitely repeated $$2\times 2$$ 2 × 2 zero-sum games. With the widespread use of learning algorithms, such problems are becoming increasingly necessary and significant; however, related theoretical results are very rare. In this study, we first demonstrate that the stage strategy given by the Hedge algorithm can be represented by a scalar, which we define as the state. We then build the State Transition Triangle Graph (STTG) and reformulate the algorithm exploitation problem as the longest path problem on the STTG. This problem can be solved via the Bellman Optimality Equation. However, this approach is computationally expensive, especially for repeated games with large time horizons. To address this issue and further investigate the system dynamics, we study the game system driven by the Hedge algorithm and myopic best response, demonstrating its periodic behavior. By comparing payoffs, we derive a recurrence relation between the optimal actions at time-adjacent states and ultimately prove that the globally optimal strategy also leads to cyclic behavior. Our subsequent work suggests that the results in this paper are general, providing insights for general games and algorithms.