Recall that the Follow-the-Leader opponent plays the best action in retrospect, defined as the action that would have achieved the highest payoff against our entire history of play. For this opponent, our strategy will be to learn a best response to each action, and then use the well-known ellipsoid algorithm to predict the opponent’s actions while playing best responses to the predicted actions.

\ Using Ellipsoid for Prediction

\ Note that while the bound on the number of losses and ties we incur is exponential, the runtime can be considered efficient since choosing which action to play in each round is efficient; this is an improvement over the simple general prediction algorithm we considered in section 3, which requires considering an exponential number of game matrices to choose which action to play in a single round. We also consider a limited-history variant of the Follow-the-Leader opponent below, against which we can achieve a polynomial bound on losses and ties.

4.4.1 Variant: Limited History

4.5 Highest Average Payoff Opponent

The Highest Average Payoff opponent plays the action that has achieved the highest average payoff over the times they have played it. We discuss this opponent in A.4.

:::info This paper is available on arxiv under CC BY 4.0 DEED license.

:::

Feed: Hacker Noon - Medium

View: Original article