Multi-Armed Bandit

The core challenge of reinforcement learning lies in the exploration-exploitation tradeoff, where agents need to find a balance between exploiting known effective strategies and exploring unknown possibilities.

PORTAL draws on the best-arm identification idea from multi-armed bandits; the goal is not to maximize cumulative reward but to identify the currently best candidate with the fewest queries.

The exploration-exploitation trade-off directly determines whether an algorithm can converge to the global optimum, and it is also the main subject of study in the multi-armed bandit problem.

This equivalence is currently established in the multi-armed bandit rather than the full MDP setting, so the conclusions mainly apply to static or approximately static decision problems.

The researchers proved a mathematical equivalence: collective decision-making through local imitation (such as bees choosing a nest site via the waggle dance) is exactly equivalent to single-agent reinforcement learning (RL) in the multi-armed bandit setting.

The multi-armed bandit is the simplest decision model in reinforcement learning, in which an agent chooses one of a fixed K actions to obtain an immediate reward, with no state transitions.

UCB (Upper Confidence Bound) is a classic multi-armed bandit algorithm whose core idea is to add a confidence upper bound term to the estimated expected reward of each action and preferentially choose the action with the highest upper bound to balance exploration and exploitation.

Regret in multi-armed bandits is defined as T times the expected reward of the optimal arm after T rounds of play minus the total expected reward obtained by the actual policy.

The multi-armed bandit (MAB) is a classic framework in reinforcement learning and online decision-making, in which a player faces K arms, each arm's reward follows an unknown distribution, and the goal is to minimize cumulative regret.

The lower bound for the standard multi-armed bandit problem is O(√T), and ORUCB's extra log(T+1) factor stems from the complexity introduced by simultaneously learning the correction function.

Thompson Sampling models the posterior reward probability of each arm in the multi-armed bandit problem using a Beta distribution, samples from the posterior each round and selects the arm with the highest sampled value, and achieves a theoretically better regret bound than ε-greedy.

In the multi-armed bandit problem, Thompson Sampling each round samples a value from the Beta posterior distribution of each arm, selects the arm with the largest sampled value to execute, and thereby achieves a balance between exploration and exploitation.