Machine Learning 101 P18: Upper Confidence Bound (UCB)

The Multi-Armed Bandit (MAB) Problem

This is a classic reinforcement learning problem, where an agent must choose mong multiple options over time to maximize the total reward. But what is reinforcement learning in the first place?

Reinforcement Learning is a type of machine learning where an agent learns by interacting with an environment to maximize a reward. Unlike supervised learning (where we provide labeled data), reinforcement learning learns from trial and error. It consists of 5 main elements:

• Agent: AI model.
• Environment: the environment that the agent interacts with.
• State: The current situation of the agent in the environment.
• Action: The choices that the agent make at any state.
• Reward: Feedback given for an active (either positive or negative).

The goal of any reinforcement learning model is to learn any optimal strategy (policy) to maximise long-term rewards. Reinforcement learning faces these 2 classic dilemma, of which the balance plays the key role in influencing the long-term strategy:

• Exploration: Trying new actions in order to find better strategies.
• Exploitation: Using the best acquired action to maximize rewards.

Getting back to the MAB problem. As mentioned, it is a problem where an agent must choose between multiple options (arms) over time to maximize the total reward. In the MAB problem, there is a trade-off between exploration and exploitation. For instance, supposing a digital marketing campaign where you have 5 different ad versions (A, B, C, D, E). Each ad has an unknown click-through rate (CTR), meaning you don’t know upfront which ad is best. Here is the scenerio, which you possess no knowledge of:

• If you always show Ad C (7%), you maximize conversions.
• But you don’t know that upfront, so you must experiment before committing.

The solution: We will use bandit algorithms that gradually learn the best option by balancing exploration and exploitation.

• Start by trying each ad randomly to gather initial data.
• Track the success rate (CTR) of each ad.
• Use an algorithm (like UCB or Thompson Sampling) to decide whether to explore a new ad or exploit the best-performing one.
• Over time, focus more on the best ad while still exploring occasionally.

Upper Confidence Bound (UCB)

Let’s not go too deep into mathematical equations here, but instead let’s look at the bigger picture of how UCB workin first:

1. Initialization: Play each arm at least once.
2. For each round:

• Compute UCB score of each arm.
• Pick the arm with the highest UCB score.
• Update statistics (mean reward, counts).

3. Repeat until a stopping condition is met (e.g., time limit).

UCB algorithm

Example

Application

• Online Ads: Deciding which ad to display for maximum clicks.
• Recommender Systems: Personalizing content for users.
• Clinical Trials: Selecting treatments that maximize patient recovery.
• Robotics: Optimizing control policies in uncertain environments.
• Finance: Portfolio optimization and algorithmic trading.

Key considerations

• UCB is a powerful and theoretically optimal bandit algorithm in a long run, just computationally expensive.
• No need hypermeter tunin, except for 1 param.
• Since it assumes that rewards are stochastic, independent and stationary, it is not ideal for non-static environments where reward distributions change over time.

Imagine using UCB to select online ads, but:

• Ad A was best in January (7% CTR), so UCB focuses on it.
• Ad B improves in February (8% CTR), but UCB is too slow to shift because it still believes Ad A is better.

Improved versions

There are several improved versions of UCB:

Let’s take a look at an example of UCB implementation for an ad selection problem with Python.

import numpy as np
import matplotlib.pyplot as plt

# Simulated environment: each ad (arm) has a fixed probability of success
true_conversion_rates = [0.1, 0.15, 0.2, 0.18, 0.25]  # The actual reward rates of each ad
num_ads = len(true_conversion_rates)
num_rounds = 1000  # Number of trials

# UCB parameters
ad_rewards = np.zeros(num_ads)  # Stores sum of rewards per ad
ad_counts = np.zeros(num_ads)   # Stores number of times each ad is chosen
total_rewards = []  # Track cumulative reward

# Run UCB
for t in range(1, num_rounds + 1):
    ucb_values = [
        (ad_rewards[i] / ad_counts[i] if ad_counts[i] > 0 else 1e6) + np.sqrt(2 * np.log(t) / (ad_counts[i] + 1e-10))
        for i in range(num_ads)
    ]
    chosen_ad = np.argmax(ucb_values)  # Select ad with highest UCB

    # Simulate user click (reward) based on the true conversion rate
    reward = np.random.rand() < true_conversion_rates[chosen_ad]

    # Update statistics
    ad_rewards[chosen_ad] += reward
    ad_counts[chosen_ad] += 1
    total_rewards.append(sum(ad_rewards))

# Plot results
plt.plot(total_rewards)
plt.xlabel("Rounds")
plt.ylabel("Total Reward")
plt.title("UCB Performance")
plt.show()

print("Final selection counts:", ad_counts)

# implementing ucb
import math
N = 10000
d = 10
ads_selected = []
numbers_of_selections = [0] * d
sums_of_rewards = [0] * d
total_reward = 0
for n in range(0, N):
  ad = 0
  max_upper_bound = 0
  for i in range(0, d):
    if (numbers_of_selections[i] > 0):
      average_reward = sums_of_rewards[i] / numbers_of_selections[i]
      delta_i = math.sqrt(3/2 * math.log(n + 1) / numbers_of_selections[i])
      upper_bound = average_reward + delta_i
    else:
      upper_bound = 1e400
    if (upper_bound > max_upper_bound):
      max_upper_bound = upper_bound
      ad = i
  ads_selected.append(ad)
  numbers_of_selections[ad] = numbers_of_selections[ad] + 1
  reward = dataset.values[n, ad]
  sums_of_rewards[ad] = sums_of_rewards[ad] + reward
  total_reward = total_reward + reward