开篇引言 / Opening
English
The most important feature distinguishing reinforcement learning from other types of learning is that it uses training information that evaluates the actions taken rather than instructs by giving correct actions. This is what creates the need for active exploration, for an explicit search for good behavior. Purely evaluative feedback indicates how good the action taken was, but not whether it was the best or the worst action possible. Purely instructive feedback, on the other hand, indicates the correct action to take, independently of the action actually taken.
中文
区分强化学习与其他学习类型的最重要特征是：它使用评价性的训练信息（评估所采取的动作），而非指导性的信息（给出正确动作）。正是这一点产生了主动探索的需要——需要显式地搜索好的行为。纯粹的评价性反馈表明所采取的动作有多好，但不表明它是否是最好的或最差的。纯粹的指导性反馈则指出应该采取的正确动作，与实际采取的动作无关。
English
In this chapter we study the evaluative aspect of reinforcement learning in a simplified setting, one that does not involve learning to act in more than one situation. This nonassociative setting avoids much of the complexity of the full reinforcement learning problem. The particular problem that we explore is a simple version of the k-armed bandit problem.
中文
在本章中，我们在一个简化的环境中研究强化学习的评价性方面——该环境不涉及在多种情境下学习行动。这种非关联性环境避免了完整强化学习问题的大部分复杂性。我们探索的具体问题是k-臂老虎机问题的一个简单版本。
2.1 k-臂老虎机问题 / A k-armed Bandit Problem
English
You are faced repeatedly with a choice among k different options, or actions. After each choice you receive a numerical reward chosen from a stationary probability distribution that depends on the action you selected. Your objective is to maximize the expected total reward over some time period, for example, over 1000 action selections, or time steps.
中文
你反复面临从 k 个不同选项（或动作）中做出选择的局面。每次选择后，你会收到一个数值奖励，该奖励从依赖于你所选动作的平稳概率分布中抽取。你的目标是在某段时间内（例如1000次动作选择，即时间步）最大化期望总奖励。
English
This is the original form of the k-armed bandit problem, so named by analogy to a slot machine, or "one-armed bandit," except that it has k levers instead of one. Each action selection is like a play of one of the slot machine's levers, and the rewards are the payoffs for hitting the jackpot.
中文
这就是k-臂老虎机问题的原始形式——如此命名是因为类比于老虎机（"单臂老虎机"），只不过它有k个拉杆而非一个。每次动作选择就像拉一次老虎机的拉杆，奖励就是中大奖的收益。
动作价值 / Action Values
English
Each of the k actions has an expected or mean reward given that that action is selected; let us call this the value of that action. We denote the action selected on time step t as At, and the corresponding reward as Rt. The value of an arbitrary action a, denoted q*(a), is the expected reward given that a is selected:
中文
k个动作中的每一个都有一个期望或平均奖励（当该动作被选择时）；我们称之为该动作的价值（value）。我们用 At 表示时间步t选择的动作，对应的奖励为 Rt。任意动作a的价值记为 q*(a)，是在选择a时的期望奖励：
q*(a) = E[Rt | At = a]
贪婪动作与探索 / Greedy Actions and Exploration
English
If you maintain estimates of the action values, then at any time step there is at least one action whose estimated value is greatest. We call these the greedy actions. When you select one of these actions, we say that you are exploiting your current knowledge. If instead you select one of the nongreedy actions, then we say you are exploring. Exploitation is the right thing to do to maximize the expected reward on the one step, but exploration may produce the greater total reward in the long run.
中文
如果你维护动作价值的估计，那么在任何时间步至少有一个动作的估计价值最大。我们称这些为贪婪（greedy）动作。当你选择其中之一时，我们说你在利用（exploiting）当前知识。如果你选择了非贪婪动作，我们说你在探索（exploring）。利用是在一步中最大化期望奖励的正确做法，但探索可能在长期内产生更大的总奖励。
2.2 动作价值方法 / Action-value Methods
English
One natural way to estimate action values is by averaging the rewards actually received — the sample-average method:
中文
估计动作价值的一种自然方法是对实际收到的奖励取平均——即样本平均方法：
Qt(a) = (a被选前获得的奖励之和) / (a被选前的次数)
贪婪动作选择 / Greedy Action Selection
English
The simplest action selection rule is to select one of the actions with the highest estimated value — the greedy method:
中文
最简单的动作选择规则是选择估计价值最高的动作之一——贪婪方法：
At = argmaxa Qt(a)
ε-贪婪方法 / ε-greedy Methods
English
A simple alternative is to behave greedily most of the time, but every once in a while, say with small probability ε, instead select randomly from among all the actions with equal probability. We call methods using this rule ε-greedy methods. An advantage is that, in the limit as the number of steps increases, every action will be sampled an infinite number of times, ensuring convergence.
中文
一个简单的替代方案是大多数时候贪婪行动，但偶尔以很小的概率 ε 从所有动作中等概率随机选择。使用这一规则的方法称为ε-贪婪方法。其优势在于：随着步数增加到无穷，每个动作都会被采样无限次，从而确保收敛。
2.3 10-臂测试平台 / The 10-armed Testbed
English
To assess the relative effectiveness of greedy and ε-greedy methods, they were compared on a suite of 2000 randomly generated k-armed bandit problems with k=10. For each problem, the action values q*(a) were selected from a normal distribution with mean 0 and variance 1, and the actual rewards were selected from a normal distribution with mean q*(At) and variance 1.
中文
为了评估贪婪方法和ε-贪婪方法的相对有效性，在2000个随机生成的k=10的老虎机问题上进行了对比。每个问题的动作价值q*(a)从均值0、方差1的正态分布中选取，实际奖励从均值q*(At)、方差1的正态分布中抽取。
English
The greedy method improved slightly faster at the very beginning, but then leveled off at a lower level, achieving a reward-per-step of only about 1, compared with the best possible of about 1.55. The greedy method performed significantly worse in the long run because it often got stuck performing suboptimal actions. The ε-greedy methods eventually performed better because they continued to explore.
中文
贪婪方法在最开始改进稍快，但随后停滞在较低水平，每步奖励仅约1，而最佳可能约1.55。贪婪方法长期表现明显更差，因为它经常陷入次优动作。ε-贪婪方法最终表现更好，因为它们持续探索，不断改善识别最优动作的机会。
关键发现：ε=0.1 的方法探索更多，通常更早找到最优动作，但永远不会超过91%的时间选择它。ε=0.01 的方法改进更慢，但最终在两个指标上都会超过ε=0.1。也可以随时间递减ε来兼顾两者优势。
2.4 增量式实现 / Incremental Implementation
English
The action-value methods estimate action values as sample averages. These averages can be computed efficiently with constant memory and constant per-time-step computation using an incremental update rule. Given Qn and the n-th reward Rn, the new average is:
中文
动作价值方法将价值估计为样本平均。这些平均可以用增量更新规则以恒定内存和每步恒定计算量高效地计算。给定 Qn 和第n个奖励 Rn，新平均值为：
Qn+1 = Qn + (1/n) [Rn − Qn]
English
This update rule is of a form that occurs frequently throughout this book. The general form is:
中文
这一更新规则的形式在本书中反复出现。通用形式为：
NewEstimate ← OldEstimate + StepSize × [Target − OldEstimate]
English
The expression [Target − OldEstimate] is an error in the estimate. It is reduced by taking a step toward the "Target."
中文
表达式 [Target − OldEstimate] 是估计中的误差。它通过向"目标"迈出一步来减小。
完整算法伪代码 / Complete Algorithm Pseudocode
A simple bandit algorithm
─────────────────────────────────────
Initialize, for a = 1 to k:
Q(a) ← 0
N(a) ← 0
Loop forever:
A ← { argmax_a Q(a) with probability 1−ε
{ random action with probability ε
R ← bandit(A)
N(A) ← N(A) + 1
Q(A) ← Q(A) + (1/N(A)) × [R − Q(A)]
2.5 跟踪非平稳问题 / Tracking a Nonstationary Problem
English
For nonstationary problems, it makes sense to give more weight to recent rewards than to long-past rewards. One popular way is to use a constant step-size parameter α:
中文
对于非平稳问题，给近期奖励更高的权重是合理的。一种流行的方法是使用恒定步长参数 α：
Qn+1 = Qn + α [Rn − Qn]
English
This results in Qn+1 being an exponential recency-weighted average of past rewards and the initial estimate. The weight given to each reward decays exponentially based on how long ago it was observed.
中文
这使得 Qn+1 成为过去奖励和初始估计的指数近因加权平均。给予每个奖励的权重根据其被观测的时间远近呈指数衰减。
English
The convergence conditions from stochastic approximation theory require: Σαn(a) = ∞ and Σα²n(a) < ∞. The sample-average case (αn=1/n) meets both, but the constant step-size case (αn=α) does not meet the second — meaning estimates never fully converge, which is actually desirable in nonstationary environments.
中文
随机逼近理论的收敛条件要求：Σαn(a) = ∞ 且 Σα²n(a) < ∞。样本平均情形（αn=1/n）满足两者，但恒定步长情形（αn=α）不满足第二个条件——意味着估计永远不会完全收敛，这在非平稳环境中实际上是我们期望的。
2.6 乐观初始值 / Optimistic Initial Values
English
Initial action values can be used as a simple way to encourage exploration. Suppose we set all initial action values to +5 instead of zero. The q*(a) in the 10-armed testbed are selected from a normal distribution with mean 0, so +5 is wildly optimistic. Whichever actions are initially selected, the reward is less than the starting estimates; the learner switches to other actions, being "disappointed." The result is that all actions are tried several times before the value estimates converge.
中文
初始动作价值可以作为一种简单的鼓励探索的方式。假设我们将所有初始值设为 +5 而非零。10-臂测试平台中的 q*(a) 来自均值0的正态分布，因此+5是极度乐观的。无论最初选择哪个动作，奖励都低于起始估计；学习者会切换到其他动作，因为感到"失望"。结果是在价值估计收敛之前，所有动作都会被尝试多次。
English
We call this technique optimistic initial values. It is a simple trick that can be quite effective on stationary problems, but it is far from generally useful. For nonstationary problems, its drive for exploration is inherently temporary.
中文
我们称这种技术为乐观初始值。这是一个简单的技巧，在平稳问题上非常有效，但远非普遍适用。对于非平稳问题，它的探索驱动力本质上是暂时的。
2.7 置信上界动作选择 / Upper-Confidence-Bound Action Selection
English
Exploration is needed because there is always uncertainty about the accuracy of the action-value estimates. ε-greedy forces non-greedy actions to be tried, but indiscriminately. It would be better to select among the non-greedy actions according to their potential for actually being optimal. One effective way is UCB action selection:
中文
探索是必要的，因为动作价值估计的准确性始终存在不确定性。ε-贪婪强制尝试非贪婪动作，但不加区分。更好的做法是根据非贪婪动作实际成为最优的可能性来选择。一种有效的方法是UCB（置信上界）动作选择：
At = argmaxa [ Qt(a) + c √(ln t / Nt(a)) ]
English
The square-root term is a measure of the uncertainty in the estimate of a's value. The quantity being maximized is thus a sort of upper bound on the possible true value of action a, with c determining the confidence level. Each time a is selected, uncertainty decreases; each time another action is selected, a's uncertainty increases.
中文
平方根项是对动作a价值估计不确定性的度量。因此被最大化的量是动作a可能真实价值的一种上界，c决定了置信水平。每次选择a时不确定性降低；每次选择其他动作时，a的不确定性增加。
局限性：UCB在老虎机问题上表现良好，但比ε-贪婪更难扩展到更一般的强化学习设置。主要困难包括处理非平稳问题和使用函数近似时的大状态空间。
2.8 梯度老虎机算法 / Gradient Bandit Algorithms
English
Instead of estimating action values, we can learn a numerical preference Ht(a) for each action. The larger the preference, the more often that action is taken, but the preference has no interpretation in terms of reward. Action probabilities are determined by a soft-max distribution (Gibbs/Boltzmann):
中文
我们可以不估计动作价值，而是为每个动作学习一个数值偏好 Ht(a)。偏好越大，该动作被选择的频率越高，但偏好本身不直接对应奖励。动作概率由软最大化分布（Gibbs/Boltzmann分布）确定：
Pr{At=a} = eHt(a) / Σb eHt(b) = πt(a)
随机梯度上升更新 / Stochastic Gradient Ascent Update
English
On each step, after selecting action At and receiving reward Rt, the preferences are updated:
中文
每步选择动作 At 并获得奖励 Rt 后，偏好按如下更新：
Ht+1(At) = Ht(At) + α(Rt − R̄t)(1 − πt(At))
Ht+1(a) = Ht(a) − α(Rt − R̄t)πt(a), for all a ≠ At
English
The R̄t term serves as a baseline. If the reward is higher than the baseline, the probability of taking At in the future is increased; if below, it is decreased. The non-selected actions move in the opposite direction. The algorithm can be shown to be an instance of stochastic gradient ascent.
中文
R̄t 项充当基线（baseline）。如果奖励高于基线，未来选择 At 的概率增加；如果低于基线，概率降低。未被选择的动作则朝相反方向移动。可以证明该算法是随机梯度上升的一个实例。
2.9 关联搜索（上下文老虎机）/ Associative Search (Contextual Bandits)
English
So far we have considered only nonassociative tasks. In a general RL task there is more than one situation, and the goal is to learn a policy: a mapping from situations to the best actions. Suppose there are several different k-armed bandit tasks, and on each step you confront one chosen at random along with a distinctive clue about its identity (e.g., a color). Now you can learn a policy: if red, select arm 1; if green, select arm 2.
中文
到目前为止我们只考虑了非关联性任务。在一般RL任务中有多种情境，目标是学习一个策略：从情境到最佳动作的映射。假设有多个不同的k-臂老虎机任务，每步随机面对一个并附带其身份的独特线索（如颜色）。你现在可以学习策略：红色时选臂1；绿色时选臂2。
English
This is an associative search task, now often called contextual bandits. These are intermediate between the k-armed bandit problem and the full RL problem. They involve learning a policy (like full RL), but each action affects only the immediate reward (like the bandit problem). If actions are allowed to affect the next situation as well as the reward, then we have the full reinforcement learning problem.
中文
这就是关联搜索任务，现在通常称为上下文老虎机（contextual bandits）。它介于k-臂老虎机问题和完整RL问题之间。它涉及学习策略（类似完整RL），但每个动作仅影响即时奖励（类似老虎机问题）。如果动作不仅影响奖励还影响下一个情境，那就构成了完整的强化学习问题。
2.10 本章小结 / Summary
English
We presented several simple ways of balancing exploration and exploitation:
• ε-greedy methods choose randomly a small fraction of the time
• UCB methods choose deterministically but favor actions with fewer samples
• Gradient bandit algorithms estimate action preferences, not values, using soft-max
• Optimistic initial values cause even greedy methods to explore significantly
中文
我们介绍了几种平衡探索与利用的简单方法：
• ε-贪婪方法：在一小部分时间随机选择
• UCB方法：确定性选择，但偏好采样较少的动作
• 梯度老虎机算法：估计动作偏好而非价值，使用软最大化
• 乐观初始值：即使贪婪方法也会进行大量探索
参数研究 / Parameter Study
English
Figure 2.6 shows a parameter study comparing all algorithms as a function of their parameter. All algorithms perform best at an intermediate parameter value (inverted-U shape). All are fairly insensitive, performing well over a range of parameter values varying by about an order of magnitude. Overall, UCB seems to perform best on this problem.
中文
图2.6展示了一个参数研究，比较各算法性能随参数变化的情况。所有算法都在中间参数值处表现最佳（倒U形）。所有方法都相当不敏感，在约一个数量级的参数范围内表现良好。总体上，UCB在该问题上表现最好。
English
Despite their simplicity, the methods presented in this chapter can fairly be considered the state of the art. More sophisticated methods (e.g., Gittins index, Thompson sampling/Bayesian methods) exist, but their complexity and assumptions make them impractical for the full reinforcement learning problem.
中文
尽管简单，本章介绍的方法可以被公正地视为当前的最先进水平。更复杂的方法（如Gittins指数、Thompson采样/贝叶斯方法）确实存在，但其复杂性和假设使它们不适用于完整的强化学习问题。