Taking Myopic Best Response Against The Hedge Algorithm

With the rapid development of artificial intelligence (AI), the game between the human and machine/AI becomes more and more common. The related theoretical analysis becomes significant and necessary, which however is still rare. This problem involves evolution analysis and optimal control of dynamic game systems driven by learning algorithms. In this paper, we consider a finitely repeated two-player zero-sum game. We study the dynamic evolution process of the game system, in which one player employs the Hedge algorithm and the other player takes the myopic best response. By the updating formula of the Hedge algorithm, we define a quantity called the state and construct the State Transition Triangle Graph (STTG). Then, we prove that the game system is periodic after o(T) stages.