Action Selection in Reinforcement Learning

The Decision Repeats

Imagine facing the same kind of decision again and again. At every time step, an agent selects one option from k available actions and receives a numerical reward. The central challenge is not simply to make one good choice. It is to choose repeatedly so that the total reward collected over a specified period is as large as possible.

One Action and Its Reward

A single cycle has a clear structure. The agent selects one action from the available options. That selected action identifies the stationary probability distribution used to select the numerical reward. The agent then receives the reward and reaches the next time step, where another action must be selected.

The reward is not necessarily a fixed value that always follows an action. Instead, it is selected from the probability distribution associated with that action. Different actions can have different stationary probability distributions. Stationary means that the distribution associated with an action does not change over time.

Stationary Reward Distributions

The word stationary describes the reward distribution linked to an action, not a promise that every reward will be identical. The distribution does not change over time, but a reward is selected from that distribution whenever the action is chosen. Therefore, an action and its reward distribution are connected, while the numerical reward produced on an individual selection is drawn from that distribution.

The Total-Reward Objective

The agent's objective is to maximize expected total reward over a time period. This objective changes how the problem should be understood. The agent is not judged only by the reward from one isolated selection. Rewards from repeated decisions contribute to the total collected over the specified period.

The phrase best levers refers to actions that are most valuable for this repeated objective. However, the problem statement does not provide the action distributions in advance. Its essential structure is that every action has a distribution and the agent must repeatedly select actions while seeking greater expected total reward.

Repeated Choice Versus One-Time Choice

Common Interpretation Errors

• Treating the problem as a one-time decision

  A k-Armed Bandit Problem is defined as a repeated decision problem. After a reward is received, another choice occurs at the next time step.

  Fix: Trace the process across multiple action-reward cycles.

• Assuming an action always produces one fixed numerical reward

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

  Fix: Describe the action as determining a distribution, then describe the reward as being selected from that distribution.

• Optimizing only the next reward

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

  Fix: Consider how repeated rewards contribute to the total objective.

• Assuming stationary means the reward never varies

  Stationary means the distribution does not change over time; it does not state that every selected reward must be identical.

  Fix: Keep the stable distribution separate from the individual numerical reward selected from it.

Check Your Understanding

Key Takeaways

1. The k-Armed Bandit Problem consists of repeated choices among k possible actions. Each selected action is associated with a stationary probability distribution, and the numerical reward for that step is selected from the distribution linked to the chosen action. The agent's goal is to maximize expected total reward over a specified time period. The repeated action-reward cycle, rather than a single isolated choice, is the defining structure.