这是一个多臂老虎机问题的简单案例。正如您所注意到的，当您认为在短期内不是最理想的时候，您希望通过尝试未知硬币来平衡您收集的信息与利用您拥有的知识。

在经典的多臂老虎机问题中，您无法确定任一硬币的概率。但是，在这里你知道硬币 A 的价值，所以当你翻转 A 时，你不会得到任何信息。事实上，你不妨忽略 A 的随机性，并假设你得到一个单位$1/2$每个选择 A。这意味着如果抛硬币 A 是正确的，那么你应该继续抛 A。所以，你只想找到何时应该放弃 B的最佳停止规则。这取决于先验分布对于 B 的参数和试验次数。试验次数越多，探索就越有价值，所以你会更多地测试 B。

一般来说，我认为您无法摆脱动态规划问题，尽管可能存在可以更简单地找到和检查最优策略的特殊情况。

有了统一的先验，您应该在这里停下来：

$(0 ~ \text{heads}, 3 ~\text{tails}), (1 ~\text{head}, 5 ~\text{tails}), (2 ~\text{heads}, 6 ~\text{tails}), (3,7), (4,8),...(31,35), (32,35), (33,36), (34,37), ... (41,44), (42,44), ... (46,48), (47,48), (48,49), (49,50)$.

在此策略下，您期望收集$61.3299$头。

我使用以下 Mathematica 代码来计算股票：

Clear[Equity];
Equity[n_, heads_, tails_] := Equity[n, heads, tails] = 
    If[n == 0, heads, 
       Max[1/2 + Equity[n - 1, heads, tails], 
           (heads + 1)/(heads + tails + 2) Equity[n - 1, heads + 1, tails] + 
           (tails + 1)/(heads + tails + 2) Equity[n - 1, heads, tails + 1]
           ]
      ]

作为比较，Thompson 采样启发式（Cam Davidson Pilon 声称这是最佳的）给出了平均 60.2907 个正面，比 1.03915 低。Thompson 抽样的问题是，它有时会在您有足够的信息知道这不是一个好的赌注时对 B 进行抽样，并且通常会浪费在信息最有价值时尽早抽样 B 的机会。在这种类型的问题中，您几乎从不会对您的选择无动于衷，并且有一个纯粹的最优策略。

tp[heads_, tails_] := tp[heads, tails] = 
    Integrate[x^heads (1 - x)^tails / Beta[heads + 1, tails + 1], {x, 0, 1/2}]


Clear[Thompson];
Thompson[flipsLeft_, heads_, tails_] := Thompson[flipsLeft, heads, tails] = 
    If[flipsLeft == 0, heads, 
       Module[{p = tp[heads, tails]}, 
           p (1/2 + Thompson[flipsLeft-1,heads,tails]) + 
           (1-p)((heads+1)/(heads+tails+2)Thompson[flipsLeft-1,heads+1,tails] + 
           ((tails+1)/(heads+tails+2)) Thompson[flipsLeft-1,heads,tails+1])]]

多臂强盗

这是多臂老虎机问题的一个特例。我说一个特殊情况，因为通常我们不知道正面的任何概率（在这种情况下，我们知道其中一枚硬币的概率为 0.5）。

您提出的问题被称为探索与利用的困境：您是探索其他选择，还是坚持您认为最好的选择。假设您知道所有概率，则有一个直接的最佳解决方案：只需选择获胜概率最高的硬币。正如您所提到的，问题在于我们不确定真正的概率是多少。

关于这个主题有很多文献，也有很多确定性算法，但是既然你标记了这个贝叶斯，我想告诉你我个人最喜欢的解决方案：贝叶斯强盗！

Baysian Bandit 解决方案

这个问题的贝叶斯方法是非常自然的。我们有兴趣回答“硬币 X 在两者中更好的概率是多少？”。

先验，假设我们还没有观察到硬币翻转，我们不知道硬币 B 正面朝上的概率是多少，表示这个未知。所以我们应该为这个未知概率分配一个先验均匀分布。或者，我们对硬币 A 的先验（和后验）完全集中在 1/2。$p_B$

正如你所说，我们观察到硬币 B 有 2 个反面和 1 个正面，我们需要更新我们的后验分布。假设一个统一的先验，并且翻转是伯努利硬币翻转，我们的后验是。现在比较后验分布或 A 和 B：$Beta( 1 + 1, 1 + 2)$

寻找近似最优策略

既然我们有后路，该怎么办？我们有兴趣回答“硬币 B 在两者中更好的概率是多少”（请记住，从我们的贝叶斯角度来看，虽然有一个明确的答案，但我们只能用概率说话）：

近似最优解是有概率选择B$w_B$和 A 概率$1 - w_B$. 该方案最大化预期收益。$w_B$可以通过数值计算来计算，因为我们知道后验分布，但是一种有趣的方法如下：

1. Sample P_B from the posterior of coin B
2. If P_B > 0.5, choose coin B, else choose coin A.

这个方案也是自我更新的。当我们观察选择硬币 B 的结果时，我们用这个新信息更新我们的后验，然后再次选择。这样，如果 B 币真的很差，我们会少选它，而 B 币实际上真的很好，我们会更频繁地选择它。当然，我们是贝叶斯主义者，因此我们永远不能绝对肯定硬币 B 更好。像这样进行概率选择是探索-开发困境最自然的解决方案。

这是Thompson Sampling的一个特殊示例。更多信息和在线广告的酷应用，可以在谷歌的研究论文和雅虎的研究论文中找到。我喜欢这个东西！