Многорукий бандит

(Multi-armed bandit, MAB)

Многорукий бандит – это класс задач из области обучения с подкреплением (Reinforcement Learning).

В таких задачах агент должен делать выбор из нескольких действий, каждое из которых имеет свою вероятность выигрыша.

Примером может являться сеанс одновременной игры на нескольких игровых автоматах, каждый из которых имеет свою вероятность выигрыша. При этом важно, что эта вероятность заранее неизвестна.

Целью действий агента является получение максимального вознаграждения и постепенное накопление опыта и статистики для дальнейших шагов. В случае игры на игровых автоматах цель – получить максимальрный выигрыш.

Главная дилемма в задаче многорукого бандита:

1. Исследовать каждый автомат и опытым путем определить наиболее выгодные из них.
2. Играть на случайно выбранном автомате, который считаем наиболее выгодным.

Стратегии решения задач многорукого бандита

1. e-greedy – жадная стратегия, когда с вероятностью e выбирается определенный автомат. Или же выбирается автомат, который считается наиболее выгодным на данный момент.
2. UCB (Upper Confidence Bound) – стратегия с опорой на верхний доверительный интервал.
3. Thompson Sampling – использует байесовский подход к выбору действия.

Реализация жадной стратегии

Интерпретация:

Агент быстро обучается, какой автомат лучший, но иногда пробует другие (ε = 0.1).

Накопленное вознаграждение растет быстрее, если ε подобрано хорошо.

import numpy as np
import matplotlib.pyplot as plt

# Настоящие вероятности выигрыша автоматов
true_probs = [0.2, 0.5, 0.3]

# Кол-во автоматов
n_bandits = len(true_probs)
# Сколько всего игр
n_steps = 1000
# ε для ε-жадной стратегии
epsilon = 0.1

# Подсчёт среднего выигрыша каждого автомата
bandit_means = np.zeros(n_bandits)
bandit_counts = np.zeros(n_bandits)
total_reward = 0
rewards = []

for step in range(n_steps):
    if np.random.rand() < epsilon:
        # Exploration
        choice = np.random.randint(n_bandits)
    else:
        # Exploitation
        choice = np.argmax(bandit_means)
              
    # Симуляция выигрыша
    reward = 1 if np.random.rand() < true_probs[choice] else 0

    # Обновляем статистику
    bandit_counts[choice] += 1
    bandit_means[choice] += (reward - bandit_means[choice]) / bandit_counts[choice]
    total_reward += reward
    rewards.append(total_reward)

# Результат
print("Оценённые вероятности выигрыша:", bandit_means)
print("Сколько раз играли каждый автомат:", bandit_counts)

# График
plt.plot(rewards)
plt.xlabel("Ход")
plt.ylabel("Накопленное вознаграждение")
plt.title("Эволюция выигрыша (ε-greedy)")
plt.show()