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

Як це працює

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

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) та градієнтні бандити.