Алгоритм epsilon-greedy ($\varepsilon$-greedy) — це простий, але надзвичайно ефективний підхід для розв'язання задачі багаторукого бандита. Хоча він може бути менш стійким порівняно з деякими іншими методами для цієї конкретної задачі, його простота та універсальність забезпечують широку застосовність у сфері навчання з підкріпленням.

Як це працює

Алгоритм виконує такі кроки:

1. Ініціалізація оцінок значень дій $Q(a)$ для кожної дії $a$;
2. Вибір дії за наступним правилом:
   • З імовірністю $\varepsilon$: вибір випадкової дії (дослідження);
   • З імовірністю $1 - \varepsilon$: вибір дії з найвищою оцінкою (експлуатація).
3. Виконання дії та спостереження за винагородою;
4. Оновлення оцінки значення дії $Q(a)$ на основі отриманої винагороди;
5. Повторення кроків 2-4 протягом фіксованої кількості кроків.

Гіперпараметр $\varepsilon$ (епсилон) визначає баланс між дослідженням і експлуатацією:

• Велике $\varepsilon$ (наприклад, 0.5) стимулює більше дослідження;
• Мале $\varepsilon$ (наприклад, 0.01) сприяє експлуатації найкращої відомої дії.

Зразок коду

class EpsilonGreedyAgent:
  def __init__(self, n_actions, epsilon):
    """Initialize an agent"""
    self.n_actions = n_actions # Number of available actions
    self.epsilon = epsilon # epsilon
    self.Q = np.zeros(self.n_actions) # Estimated action values
    self.N = np.zeros(self.n_actions) # Action selection counters

  def select_action(self):
    """Select an action according to the epsilon-greedy strategy"""
    # With probability epsilon - random action
    if np.random.rand() < self.epsilon:
      return np.random.randint(self.n_actions)
    # Otherwise - action with highest estimated action value
    else:
      return np.argmax(self.Q)

  def update(self, action, reward):
    """Update the values using sample average estimate"""
    # Increasing the action selection counter
    self.N[action] += 1
    # Updating the estimated action value
    self.Q[action] += (reward - self.Q[action]) / self.N[action]

Додаткова інформація

Ефективність алгоритму $\varepsilon$-жадібного вибору значною мірою залежить від значення $\varepsilon$. Дві стратегії зазвичай використовуються для вибору цього значення:

• Фіксоване $\varepsilon$: це найбільш загальний варіант, коли значення $\varepsilon$ вибирається як константа (наприклад, 0.1);
• Зменшуване $\varepsilon$: значення $\varepsilon$ зменшується з часом відповідно до певного графіка (наприклад, починається з 1 і поступово зменшується до 0), щоб заохочувати дослідження на початкових етапах.

Підсумок

Алгоритм $\varepsilon$-жадібного вибору є базовим підходом для балансування дослідження та використання. Хоча він простий, слугує основою для розуміння більш складних стратегій, таких як верхня довірча межа (UCB) та градієнтні бандити.