Authors:
(1) Avrim Blum, Toyota Technological Institute at Chicago, IL, USA;
(2) Melissa Dutz, Toyota Technological Institute at Chicago, IL, USA. Table of Links Abstract and 1 Introduction 2 Setting and 2.1 Models of behaviorally-biased opponents 3 Preliminaries and Intuition 4.1 Myopic Best Responder and 4.2 Gambler’s Fallacy Opponent 4.3 Win-Stay, Lose-Shift Opponent 4.4 Follow-the-Leader Opponent and 4.5 Highest Average Payoff Opponent 5 Generalizing 5.1 Other Behaviorally-Biased Strategies 5.2 Exploiting an Unknown Strategy from a Known Set of Strategies 6 Future Work and References A Appendix A.1 Win-Stay Lose-Shift Variant: Tie-Stay A.2 Follow-the-Leader Variant: Limited History A.3 Ellipsoid Mistake Bounds A.4 Highest Average Payoff Opponent A. Appendix A.1 Win-Stay Lose-Shift Variant: Tie-Stay Proof. Recall that the Tie-Stay variant of the Win-Stay Lose-Shift opponent plays the same action immediately following a win or a tie, and switches to the next action in its action ordering immediately following a loss. Because each action is beaten by at least one other action, the opponent must switch after one of the actions we play in response to its current action in phase 1 (since we play each action in succession). If the opponent shifts to play a new action in round r, we won round r − 1, so the best response we record is correct. Since the opponent always shifts to the next action in its action ordering, over n shifts, they will shift through every action before finally shifting back to the first action in its action ordering. Through this process we therefore record a best response to every action, and we record the correct action ordering in step 1. We play at most n actions in response to each action the opponent plays to make it shift, and one of them must beat the opponent’s action, so we incur no more than n(n − 1) losses or ties in this phase. At the end of the above, the opponent will have shifted back to the first action of their action ordering. However, we don’t generally know in advance when this shift will occur, so the action we played (some a) may or may not have been a best response to it and we therefore can’t be sure whether the opponent will stay or shift. By playing a repeatedly, the opponent will eventually play some action twice; this will happen within n rounds since each action is beaten by at least one other action and ties with itself. However, while the opponent is shifting we must be winning, so we only incur 2 losses or ties here, when the opponent finally plays some action b twice in a row. Since we finished round 2 with the opponent tying or winning, they will repeat their action (b) again in the next round; we win that round by playing the recorded best response to b (which we showed was correct) in phase 3. At the start of phase 4, we predict correctly because we won the previous round and know the opponent will shift to the next action in its order (which we showed we recorded correctly). We showed earlier that we recorded correct best responses, so we win by playing the recorded best response to the predicted action. The same conditions hold for every remaining round, so we win all remaining rounds. This paper is available on arxiv under CC BY 4.0 DEED license. Authors: (1) Avrim Blum, Toyota Technological Institute at Chicago, IL, USA; (2) Melissa Dutz, Toyota Technological Institute at Chicago, IL, USA. Authors: Authors: (1) Avrim Blum, Toyota Technological Institute at Chicago, IL, USA; (2) Melissa Dutz, Toyota Technological Institute at Chicago, IL, USA. Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 2 Setting and 2.1 Models of behaviorally-biased opponents 2 Setting and 2.1 Models of behaviorally-biased opponents 3 Preliminaries and Intuition 3 Preliminaries and Intuition 4.1 Myopic Best Responder and 4.2 Gambler’s Fallacy Opponent 4.1 Myopic Best Responder and 4.2 Gambler’s Fallacy Opponent 4.3 Win-Stay, Lose-Shift Opponent 4.3 Win-Stay, Lose-Shift Opponent 4.4 Follow-the-Leader Opponent and 4.5 Highest Average Payoff Opponent 4.4 Follow-the-Leader Opponent and 4.5 Highest Average Payoff Opponent 5 Generalizing 5.1 Other Behaviorally-Biased Strategies 5.1 Other Behaviorally-Biased Strategies 5.2 Exploiting an Unknown Strategy from a Known Set of Strategies 5.2 Exploiting an Unknown Strategy from a Known Set of Strategies 6 Future Work and References 6 Future Work and References A Appendix A.1 Win-Stay Lose-Shift Variant: Tie-Stay A.1 Win-Stay Lose-Shift Variant: Tie-Stay A.2 Follow-the-Leader Variant: Limited History A.2 Follow-the-Leader Variant: Limited History A.3 Ellipsoid Mistake Bounds A.3 Ellipsoid Mistake Bounds A.4 Highest Average Payoff Opponent A.4 Highest Average Payoff Opponent A. Appendix A.1 Win-Stay Lose-Shift Variant: Tie-Stay Proof . Recall that the Tie-Stay variant of the Win-Stay Lose-Shift opponent plays the same action immediately following a win or a tie, and switches to the next action in its action ordering immediately following a loss. Because each action is beaten by at least one other action, the opponent must switch after one of the actions we play in response to its current action in phase 1 (since we play each action in succession). If the opponent shifts to play a new action in round r, we won round r − 1, so the best response we record is correct. Since the opponent always shifts to the next action in its action ordering, over n shifts, they will shift through every action before finally shifting back to the first action in its action ordering. Through this process we therefore record a best response to every action, and we record the correct action ordering in step 1. We play at most n actions in response to each action the opponent plays to make it shift, and one of them must beat the opponent’s action, so we incur no more than n(n − 1) losses or ties in this phase. Proof At the end of the above, the opponent will have shifted back to the first action of their action ordering. However, we don’t generally know in advance when this shift will occur, so the action we played (some a) may or may not have been a best response to it and we therefore can’t be sure whether the opponent will stay or shift. By playing a repeatedly, the opponent will eventually play some action twice; this will happen within n rounds since each action is beaten by at least one other action and ties with itself. However, while the opponent is shifting we must be winning, so we only incur 2 losses or ties here, when the opponent finally plays some action b twice in a row. Since we finished round 2 with the opponent tying or winning, they will repeat their action (b) again in the next round; we win that round by playing the recorded best response to b (which we showed was correct) in phase 3. At the start of phase 4, we predict correctly because we won the previous round and know the opponent will shift to the next action in its order (which we showed we recorded correctly). We showed earlier that we recorded correct best responses, so we win by playing the recorded best response to the predicted action. The same conditions hold for every remaining round, so we win all remaining rounds. This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Techniques to Beat the Tie-Stay Variant of Win-Stay, Lose-Shift

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

References: Spectral Estimation, Signal Processing, and Quantum Computing

Algorithm 8’s Approach to Countering the Highest Average Payoff Opponent

A Guide to Exploiting Unknown Strategies From a Known Bias Set

Broader Insights into Exploitable Strategies in Zero-Sum Games

Ways to Counter Limited-History Opponents with Algorithmic Tools

Ellipsoid Algorithms as a Tool Against Predictable Opponents

References: Spectral Estimation, Signal Processing, and Quantum Computing

Algorithm 8’s Approach to Countering the Highest Average Payoff Opponent

A Guide to Exploiting Unknown Strategies From a Known Bias Set

Broader Insights into Exploitable Strategies in Zero-Sum Games

Ways to Counter Limited-History Opponents with Algorithmic Tools

Ellipsoid Algorithms as a Tool Against Predictable Opponents

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps