Action selection methods in Multi-Arm bandit problems

In the world of decision-making under uncertainty, bandit problems offer a simple yet powerful framework. They serve as the foundation for understanding more complex reinforcement learning algorithms and are widely used in real-world applications like online recommendation systems, clinical trials, and adaptive A/B testing.

But to truly understand how agents make decisions in these environments, we must explore how they select actions given a situation.

What are Bandit problems?

Bandit problems are a widely studied framework for modeling sequential decision-making in environments that are non-associative — meaning there is only a single, fixed situation or context in which decisions are made.

Unlike more complex reinforcement learning settings where the agent navigates through various states, bandit problems involve repeatedly choosing from a set of actions (or “arms”) without the presence of changing states or observations. Each action yields a reward drawn from an unknown and possibly stochastic distribution, and the goal is to maximize the total reward over time.

The Role of Q-values

At the core of every action selection strategy lies a simple but powerful idea: estimating the value of each action.

This estimate is known as the Q-value, typically written as:

Qₜ(a): the estimated average reward of action *a* at time *t*

In other words, Q-values represent the agent’s current belief about how rewarding each action is, based on past experience.

These estimates are continuously updated as the agent observes more rewards over time. In the early stages, Q-values may be highly inaccurate due to limited data. But with enough exploration, they become more reliable — guiding the agent toward better, more informed decisions.

Understanding Q-values is essential, as they’re the foundation of nearly every algorithm used in bandit problems and broader reinforcement learning.

Action selection methods

Action selection methods in bandit problems govern the balance between:

• Exploration: trying different actions to gather more information about their reward distributions.
• Exploitation: choosing the best-known action to maximize immediate reward.

These methods not only influence how efficiently an agent learns about the current environment but also determine how well the system can adapt to changes in the reward distributions over time. In dynamic settings where the rewards associated with actions may increase or decrease over time, the effectiveness of an action selection strategy depends on how quickly and accurately it can detect these shifts and adjust its behavior accordingly. As a result, the design of the action selection mechanism plays a crucial role in the overall performance and responsiveness of bandit algorithms, especially in non-stationary or real-world environments.

Types of Action selection methods

There are numerous action selection methods used in bandit problems, each with its own approach to managing the exploration-exploitation trade-off. However, a common underlying pattern emerges among them. Most methods are extensions or variations of three foundational strategies:

1. Greedy Method
2. Epsilon Greedy method
3. Upper confidence bound method

Let’s Break Down the Core Strategies

1. Greedy Method

The greedy method always selects the action with the highest estimated reward:

aₜ = argmaxₐ Qₜ(a)

It’s simple and efficient — but there’s a downside. If the agent makes inaccurate estimates early on, it might never explore better actions. This method does not explore, it only exploits what it currently believes to be best.

2. Epsilon-Greedy Method

To overcome the greedy method’s limitations, epsilon-greedy introduces controlled randomness.

With a small probability ε, the agent chooses a random action. The rest of the time (1 − ε), it picks the action with the highest estimated reward:

aₜ =
  random action        with probability ε  
  argmaxₐ Qₜ(a)        with probability 1 − ε

For example, if ε = 0.1, the agent explores 10% of the time and exploits 90% of the time. This simple tweak helps prevent the agent from getting stuck in a suboptimal strategy too early.

3. Upper Confidence Bound (UCB)

UCB takes a more refined approach by adding an exploration bonus to each action’s Q-value. This bonus prioritizes actions that are both promising and under-explored:

aₜ = argmaxₐ [ Qₜ(a) + c × sqrt(ln t / Nₜ(a)) ]

Where:

• Nₜ(a) is the number of times action a has been selected by time t
• ln t (natural log of t) ensures that exploration diminishes over time
• c is a constant that controls how much exploration is encouraged

In the UCB formula below, you’ll notice that the exploration term is a function of the total number of iterations (t) and the number of times a particular action a has been selected (N_t(a)). As N_t(a) increases, the bonus decreases, which naturally shifts focus toward exploitation over time. This mechanism allows the algorithm to initially explore all actions and gradually concentrate on those that consistently perform well.

In the UCB algorithm, the parameter c controls how much the agent prioritizes exploration over exploitation. It must always be greater than zero — a non-positive value would completely eliminate exploration, defeating the purpose of UCB.

There’s no single “best” value for ccc; it’s typically tuned empirically based on the problem at hand. However, some general guidelines can help:

• Small values (e.g., 0.1 to 1) lean toward exploitation. The agent converges quickly, but risks settling on suboptimal actions if early estimates are misleading.
• Moderate values (e.g., 1 to 3) offer a more balanced trade-off, allowing for meaningful exploration while still leveraging known good actions.
• Larger values (e.g., 5 or more) lead to aggressive exploration, which can slow down convergence but helps the agent avoid being misled by early noise or randomness.

Choosing the right c value depends on your specific environment — stationary vs. non-stationary rewards, the number of actions, and how noisy the feedback is. Like most hyperparameters in machine learning, it’s something you’ll likely need to experiment with.

Final Thoughts

While these three methods — Greedy, Epsilon-Greedy, and UCB — are foundational, they’re just the beginning. Many advanced strategies build on them, including: Bayesian UCB, Sliding-Window UC, Decay-based Epsilon-Greedy, and more.

Each is designed to handle specific challenges, such as shifting reward distributions or limited memory.