Expected Reward and Decision Making

The Decision Repeats

Imagine facing the same kind of decision again and again. On every round, you choose one option from k available options, and that choice produces a numerical reward. The central challenge is not simply to make one good choice. It is to keep choosing over a period of time so that the total reward collected is as large as possible.

One Choice or Many Rounds

In the one-time case, there is no later decision in the process described here. In the k-Armed Bandit Problem, every reward is followed by another opportunity to choose. Each action selection therefore has two roles: it produces a reward for the current round, and it is part of a longer sequence whose rewards contribute to the total over the specified time period.

Actions Select Reward Distributions

A single cycle has a clear structure. First, the agent selects one action from the k available actions. The selected action determines which stationary probability distribution is used to choose the numerical reward. After the reward is received, the agent faces another choice at the next time step.

Tracing Several Rounds

The trace shows why the problem is about decision making over time. A reward from one round does not end the process. The agent must make another selection, receive another reward, and continue contributing to the total reward. Repeating the process also supplies experience about the available choices while rewards continue to accumulate.

Accumulating the Objective

The agent's objective is to maximize expected total reward over a specified time period. This objective evaluates the sequence of decisions together rather than judging only one action in isolation. A choice is valuable in the context of the repeated process because its reward contributes to the total collected during the period.

Common Misunderstandings

• Treating each action as if it always produces one fixed reward.

  The reward is selected from the probability distribution associated with the selected action.

  Fix: Remember that an action determines a stationary probability distribution, and the numerical reward is selected from that distribution.

• Treating a bandit problem as a one-time choice.

  The k-Armed Bandit Problem requires repeated choices, with another decision at the next time step after a reward is received.

  Fix: Track the sequence of actions and rewards across the specified time period.

• Optimizing only the reward from the current round.

  The stated objective is to maximize expected total reward over a time period.

  Fix: Evaluate decisions by how they contribute to the expected total reward across repeated rounds.

• Assuming every action has the same reward distribution.

  Different actions can have different stationary probability distributions.

  Fix: Keep the selected action linked to its own stationary probability distribution.

The Lever Analogy

The problem is named after a slot machine with multiple levers. Each lever represents an available action, and repeatedly selecting levers produces rewards over time. The phrase best levers refers to the actions that are most valuable for the repeated-decision objective. Treatment selection provides another analogy: a decision-maker repeatedly selects among available options and considers the rewards associated with those selections.

Practice the Decision Cycle

Key Takeaways

1. A k-Armed Bandit Problem presents k possible actions and requires the agent to choose repeatedly.
2. The selected action determines the stationary probability distribution from which a numerical reward is selected.
3. A stationary distribution does not change over time, although different actions can have different stationary distributions.
4. The agent seeks to maximize expected total reward over a specified time period, not merely the reward from one choice.
5. The repeated action-and-reward cycle distinguishes the bandit problem from a one-time decision.