Le banc d'essai à dix bras

25 novembre 2024

Il s’agit d’une méthode pour évaluer les stratégies du problème du bandit à plusieurs bras ¹. Le banc d’essai fonctionne comme suit :

Générer $10$ moyennes de récompense $μ_{i}$ associées à $10$ actions $a_{i}$
À chaque itération, permettre à l’agent de choisir une action $a_{j}$ et de recevoir une récompense $r_{t} \sim N (μ_{j}, 1)$ .

Nous répétons cela pour $100$ ensembles de $μ_{i}$ échantillonnés aléatoirement. L’objectif de l’agent est de maximiser les récompenses moyennes. Idéalement, il devrait apprendre quelle action a la moyenne la plus élevée et échantillonner à partir de celle-ci.

Stratégie 1 : $\epsilon$-greedy

class GreedyEpsilon:
    def __init__(self, n_actions, eps, reward_fn, bias=0.0):
        self.n_actions = n_actions
        self.Q = np.array([bias] * n_actions)
        self.n_moves = np.zeros((n_actions,))
        self.eps = eps
        self.reward_fn = reward_fn
        self.total_reward = 0.0

    def step(self):
        if np.random.rand() < self.eps:
            action = np.random.randint(0, self.n_actions)
        else:
            action = np.argmax(self.Q)

        reward = self.reward_fn(action)
        self.n_moves[action] += 1

        self.Q[action] += 1.0 / self.n_moves[action] * (reward - self.Q[action])
        self.total_reward += reward
        return reward

Stratégie 2 : Tricher avec le système

Nous ne sommes pas censés échantillonner plus d’une fois, mais nous le ferons pour illustrer une limite supérieure de performance.

class CheatingModel:
    def __init__(self, n_actions, eps, reward_fn, bias=0.0):
        self.n_actions = n_actions
        self.reward_fn = reward_fn
        self.total_reward = 0.0

    def step(self):
        reward = max(self.reward_fn(action) for action in range(self.n_actions))
        self.total_reward += reward
        return reward

Résultats

Code complet (version matplotlib)

import numpy as np
from tqdm import trange
import matplotlib.pyplot as plt

def normal_reward(action, action_to_reward_mu, reward_std, n_samples):
    return np.random.normal(action_to_reward_mu[action], reward_std, n_samples)

class CheatingModel:
    def __init__(self, n_actions, eps, reward_fn, bias=0.0):
        self.n_actions = n_actions
        self.reward_fn = reward_fn
        self.total_reward = 0.0

    def step(self):
        reward = max(self.reward_fn(action) for action in range(self.n_actions))
        self.total_reward += reward
        return reward

class GreedyEpsilon:
    def __init__(self, n_actions, eps, reward_fn, bias=0.0):
        self.n_actions = n_actions
        self.Q = np.array([bias] * n_actions)
        self.n_moves = np.zeros((n_actions,))
        self.eps = eps
        self.reward_fn = reward_fn
        self.total_reward = 0.0

    def step(self):
        if np.random.rand() < self.eps:
            action = np.random.randint(0, self.n_actions)
        else:
            action = np.argmax(self.Q)

        reward = self.reward_fn(action)
        self.n_moves[action] += 1

        self.Q[action] += 1.0 / self.n_moves[action] * (reward - self.Q[action])
        self.total_reward += reward
        return reward

def main():
    N_ACTIONS = 10
    N_DISTRIBUTIONS = 100
    reward_std = 1.0

    n_steps = 2000
    epsilon_values = [0.0, 0.01, 0.1, 0.2]
    avg_rewards = {epsilon: np.zeros((n_steps,)) for epsilon in epsilon_values}
    avg_rewards["cheating"] = np.zeros((n_steps,))

    bias_values = [0.0, 0.5, 1.0]
    avg_rewards_bias = {bias: np.zeros((n_steps,)) for bias in bias_values}

    for _ in trange(N_DISTRIBUTIONS):
        action_to_reward_mu = np.random.normal(0, 1, (N_ACTIONS,))
        for epsilon in epsilon_values:
            model = GreedyEpsilon(
                N_ACTIONS,
                epsilon,
                lambda a: normal_reward(a, action_to_reward_mu, reward_std, 1),
            )
            for n in range(n_steps):
                model.step()
                avg_rewards[epsilon][n] += model.total_reward / (n + 1)
            avg_rewards[epsilon] /= N_DISTRIBUTIONS

        cheating_model = CheatingModel(
            N_ACTIONS,
            0,
            lambda a: normal_reward(a, action_to_reward_mu, reward_std, 1),
        )
        for n in range(n_steps):
            cheating_model.step()
            avg_rewards["cheating"][n] += cheating_model.total_reward / (n + 1)
        avg_rewards["cheating"] /= N_DISTRIBUTIONS

        for bias in bias_values:
            biased_model = GreedyEpsilon(
                N_ACTIONS,
                0.01,
                lambda a: normal_reward(a, action_to_reward_mu, reward_std, 1),
                bias=bias,
            )
            for n in range(n_steps):
                biased_model.step()
                avg_rewards_bias[bias][n] += biased_model.total_reward / (n + 1)
            avg_rewards_bias[bias] /= N_DISTRIBUTIONS

    plt.figure(figsize=(12, 6))
    plt.subplot(1, 2, 1)
    for epsilon in epsilon_values:
        plt.plot(avg_rewards[epsilon], label=f"epsilon={epsilon}")
    plt.plot(avg_rewards["cheating"], label="modèle tricheur", linestyle="--")

    plt.legend()

    plt.yscale("log")
    plt.title("Résultats pour Epsilon")

    plt.subplot(1, 2, 2)
    for bias in bias_values:
        plt.plot(avg_rewards_bias[bias], label=f"bias={bias}")
    plt.plot(avg_rewards["cheating"], label="modèle tricheur", linestyle="--")

    plt.legend()
    plt.yscale("log")
    plt.title("Résultats pour Bias avec Epsilon=0.01")

    plt.tight_layout()
    plt.show()

if __name__ == "__main__":
    main()

Reinforcement Learning par Sutton et al ↩︎

←

Recettes pour Hario V60

Estimation Bayésienne des Paramètres

→