Since my PhD (game theory, but heavy in mathematical analysis and partial differential equations) I was interested in nice, simple algorithms that would beat fancy theoretical constructs. One of those happens to be regret minimization.

Suppose we want to play rock, paper, scissors for money. Each of us puts 100 EUR on the table, we play and the winner takes the money. ┬áLet’s further assume that you play rock and I play paper (so I win) and thus take the 100 EUR from the table. In this case, your regret for not playing paper is 100 (because we would have tied), but your regret for not paying scissors is 200, because you did not win.

Formally, if $$I$$, $$J$$ denote the strategy sets of the players (here $$I=J$$ and both are equal to {rock, paper, scissors}), then the regret for player 1’s action $$i$$, given the last-round moves $$i^*, j^*$$ is:

$$ \max(u(i,j^*)-u(i^*,j^*),0).$$

How do we get a strategy out of this? We initialize a counter at the beginning of the game. We play randomly in the beginning, and from the second round on, we compute the regrets for each action and divide each of these numbers by the sum of regrets of our actions. We will choose the action with a random strategy, playing with probability proportional to the normalized cumulative regret.

Let’s take a look at the code in Python:

import random
import numpy as np

# Base player that chooses a constant mixed strategy every time
class Player:
    def __init__(self):
        self.my_moves = []
        self.other_moves = []

    def move(self, strategy):
        # Input: a vector of probability distributions for actions
        # Output: a pure action
        r = random.uniform(0,1)
        n_actions = len(strategy)
        a = 0
        cumulative_proba = 0.0
        while a<n_actions-1:
            cumulative_proba += strategy[a] 
            if r < cumulative_proba: return a
            a +=1
        return a

class RegretPlayer(Player):
    def __init__(self):
        super(RegretPlayer, self).__init__()
        self.regret_sum = np.zeros(3)

    def regret(self):

        if len(self.my_moves)>0:
            my_action = self.my_moves[-1]
            his_action = self.other_moves[-1]
            return np.zeros(3)

        # Payoffs from my perspective
        my_payoff = np.zeros(3)

        # If we play the same, I don't get any payoff
        my_payoff[his_action] = 0.

        # I win when he plays scissors and I pay rock, 
        # or when I play the "next" (Rock = 0, Paper = 1, Scissors = 2)
        my_payoff[0 if his_action == 2 else his_action + 1] = 1

        # I lose when I play scissors and he plays rock, 
        # or when I play the "previous" action         
        my_payoff[2 if his_action == 0 else his_action -1] = -1

        regrets = [my_payoff[a]-my_payoff[my_action] for a in range(3)]
        regrets = np.array(regrets)
        return regrets

    def get_regret_mixed_strategy(self):
        normalize_sum = 0.0
        strategy = np.zeros(3)
        regret = self.regret()                   

        for a in range(3):
            strategy[a] = max(self.regret_sum[a],0)
            normalize_sum += strategy[a]
        # If all regrets are positive, play randomly
        if normalize_sum > 0:
            strategy = strategy / normalize_sum
            strategy = np.ones(3)/3
        self.regret_sum += regret
        return strategy            


We can simulate the game of the regret player:


import matplotlib.pyplot as plt

def payoff(my_action, his_action):
    if my_action == his_action: 
        return 0
    if his_action == 0 and my_action==2 or my_action == his_action-1:
        return -1
    return 1

def run(n_rounds = 10):
    p1 = RegretPlayer()
    p2 = Player() 
    total_p1 = 0.0
    total_p2 = 0.0
    rounds_won_p1 = 0.
    print("The match begins")
    for n in range(1,n_rounds):
        regret_strategy_p1 = p1.get_regret_mixed_strategy()
        m1 = p1.move(regret_strategy_p1)
        m2 = p2.move([0.4,0.3,0.3])
        # Players update the info of the moves
        total_p1 += payoff(m1,m2)
       #### Show results
        moves_map = {0:"Rock", 1:"Paper", 2:"Scissors"}
        print("Strategy:", regret_strategy_p1)
        print("My move: %s" % moves_map[m1])
        print("His move: %s" % moves_map[m2])
        rounds_won_p1 += 1 if payoff(m1,m2) >0 else 0
        # Plot the moves
        plt.title("Percentage of rounds won using a regret strategy")
        plt.scatter(n,rounds_won_p1/n, color = "red")
if __name__ == "__main__":
    run(n_rounds = 100)