Multi-Armed Bandit Problems 多臂老虎机问题

（不确定+最优备选）we add uncertainty to the problem of learning the best alternative to create a class of models known as multi-armed bandit problems. In bandit problems, rewards from alternatives are distributions rather than fixed amounts.

Bernoulli Bandit Problems 伯努利老虎机问题

a subclass of bandit problems in which each alternative has a fixed probability of producing a successful outcome.

（未知概率）Each of a collection of alternatives {A, B, C, D,…, N} has an unknown probability of producing a successful outcome, {pA, pB, pC, pD,…, pN}. In each period,the decision-maker chooses an alternative, K, and receives a successful outcome with probability pK.

例如，三种广告形式：第一种为情感发言，“为了走出xx，xx品牌有多卑微……”；第二种为产品发言，“xx品牌只采用新疆棉/高山土豆/……”；第三种为价格发言，“不要998，只要9块9……”。将这些广告投放到市场前，我们不知道他们触达消费者后，点击率是多少-未知概率。

To gain insight into the explore-exploit trade-off, we compare two heuristics.

  1. The first, sample-then-greedy, tries each alternative a fixed number of times, M, and thereafter chooses the alternative with the highest average payoff. To determine the size of M, we can refer back to the Bernoulli urn model and the square root rules. The standard deviation of the mean proportion is bounded above by 1/2√M.
  2. The second heuristic, an adaptive exploration rate heuristic, allocates ten initial trials to each alternative. The next twenty trials are allocated in proportions corresponding to the success rates. The second set of twenty trials could also be allocated according to the ratio of the squared success probabilities.

Bayesian Multi-Armed Bandit Problems 贝叶斯多臂老虎机问题

（先验知识）In a Bayesian bandit problem, the decision-maker has prior beliefs over the reward distributions of the alternatives. Given these prior beliefs, a decision maker can quantify the trade-off between exploration and exploitation and (in theory) make optimal decisions in each period.

A collection of alternatives {A, B, C, D,…, N} have associated reward distributions {f (A), f (B), f (C), f (D),…, f (N)}. The decision-maker has prior beliefs over each distribution. In each period, the decision-maker chooses an alternative, receives a reward, and calculates new beliefs based on the reward.

Determining the optimal action relies on a four-step process.

  1. First, we calculate the expected immediate reward from each alternative.
  2. Second, for each alternative, we update our beliefs about the reward distribution.
  3. Third, based on our new beliefs about reward distributions, we determine the best possible actions in all subsequent periods based on what we know.
  4. Last, we add the expected reward from the action in the next period to the expected rewards from the optimal future actions. That sum is known as the Gittins index. In each period, the optimal action has the largest Gittins index.

⚠️Notice that the calculation of the index quantifies the value of exploration. If we try an alternative, the Gittins index does not equal the expected reward. It equals the sum of all future rewards assuming we take optimal actions given what we have learned. Computing a Gittins index is difficult.
吉廷斯指数的计算量化了探索的价值。当我们尝试一个备选方案时，吉廷斯指数并不等于预期回报，而是等于在基于已学知识采取最优行动的前提下，所有未来回报的总和。计算吉廷斯指数是非常困难的。

（最优选择>期望收益）When taking an action, we care more about the probability that an alternative will be the best than about its expected reward. Provided there are not risks or high costs associated with actions, the model tells us to explore potentially high-reward actions even if they are low probability.