RL 2: Multi-Armed Bandits 2 - Action value estimation

Introduction

This tutorial covers action value estimation in the context of the multi-armed bandit problem, which is a fundamental concept in reinforcement learning. Understanding how to estimate action values is crucial for effectively choosing actions that maximize rewards, especially in both stationary and non-stationary environments. This guide will provide a step-by-step approach for implementing these concepts.

Step 1: Understand the Multi-Armed Bandit Problem

• The multi-armed bandit problem is a scenario where a player must choose between multiple options (arms) that provide different rewards.
• The goal is to maximize the total reward over time by balancing exploration (trying new options) and exploitation (choosing known rewarding options).
• Familiarize yourself with key terms:
  • Action Value: The expected reward from a specific action.
  • Stationary Bandits: The action values do not change over time.
  • Non-Stationary Bandits: Action values change over time, requiring adaptive strategies.

Step 2: Estimating Action Values

• Action values can be estimated using various strategies. Here are some common methods:
  • Sample Average: Calculate the average reward for each action based on past experiences.
    • Formula: [ Q(a) = \frac{1}{n} \sum_{i=1}^{n} r_i ] where ( Q(a) ) is the estimated action value, ( n ) is the number of times action ( a ) has been taken, and ( r_i ) are the rewards received.
  • Incremental Mean Update: Update the action value incrementally to avoid storing all past rewards.
    • Formula: [ Q_{n+1}(a) = Q_n(a) + \frac{1}{n} (R - Q_n(a)) ] where ( R ) is the most recent reward.

Step 3: Dealing with Stationary Bandits

• For stationary bandits, simple averaging techniques work well since the action values do not change.
• Use the sample average or incremental mean methods to maintain current estimates.

Step 4: Handling Non-Stationary Bandits

• For non-stationary bandits, adapt your action value estimation approach:
  • Weighted Average: Give more weight to recent rewards to adapt to changes.
    • Formula: [ Q_{n+1}(a) = Q_n(a) + \alpha (R - Q_n(a)) ] where ( \alpha ) (0 < ( \alpha ) ≤ 1) is the learning rate.
  • Sliding Window: Keep track of a fixed number of recent rewards, discarding older rewards to focus on the most relevant data.

Step 5: Choosing an Action

• Implement an action selection strategy based on your estimated action values:
  • Epsilon-Greedy: With probability ( \epsilon ), explore (choose randomly), and with probability ( 1-\epsilon ), exploit (choose the action with the highest estimated value).
  • Upper Confidence Bound (UCB): Select actions based on both the estimated action value and the uncertainty of that estimate.

Conclusion

In this tutorial, you learned about action value estimation in multi-armed bandits, including techniques for both stationary and non-stationary environments. Key takeaways include the methods for estimating action values and the importance of adaptive strategies. As a next step, consider exploring more advanced strategies like Thompson Sampling or reinforcement learning algorithms to further enhance your understanding and application of these concepts.