Optimistic Initial Values

[TOC]

Multi-armed Bandits 本篇主要介绍多臂赌博机问题的相关算法。

The 10-armed Testbed

每个动作的奖励呈正态分布。问题是通过trial and error 学习到最佳的动作，获取最大的reward。

图：

Epsilon Greedy Method

exploit： 每次根据 1-epsilon 的概率贪心选择已经尝试过的bandits中最大的奖励的bandit，选择greedy 动作

explore： 每次根据 epsilon 的概率尝试其他的bandit，强制选择non-greedy动作。

Optimistic Initial Values

乐观初始值算法：这个方法在开始阶段鼓励更多的探索，随着时间的增加，探索的次数越来越少。 所以在后期比e-greedy算法表现好。

图：

UCB Method

根据下面这个公式选择动作：

这个方法保证收益的同时不放弃潜在的收益。

在最初的K步时，要比epsilon-greedy表现差，这是因为UCB开始要随机选择所有动作。

图：

Gradient Bandit Algorithms

根据数值偏好选择动作。使用soft-max 分布：

公式：

动作偏好：

给定一个平均reward值，这个方法往往表现的很好。

Associative Search (Contextual Bandits)

关联搜索:

10 arm bandit 是一个简单的情况。如果动作的选择和下一个状态和奖励有关系，那么就会变成一个完全的强化学习问题。

This is an example of an associative search task, so called because it involves both trial-and-error learning to search for the best actions, and association of these actions with the situations in which they are best.

If actions are allowed to affect the next situation as well as the reward, then we have the full reinforcement learning problem.

Summary

我们讨论了几种简单的方法平衡exploration和exploitation。epsilon-greedy以小的概率epsilon选择随机的动作，以获取最大的奖励的动作。UCB每步增加选择尝试较少动作次数的动作。梯度算法不是估计动作值，而是估计动作的偏好，根据概率选择动作。

下图叫做参数研究parameter study

在评估一个方法时，我们不应该只关注它最好表现的参数设置，也应该关注参数值的敏感程度。

In assessing a method, we should attend not just to how well it does at its best parameter setting, but also to how sensitive it is to its parameter value.

在Ten Arm Bandits这个问题中，UCB算法表现是最好的。

Historical Remarks

Bandit Problems 在统计，工程，心理学中有研究。

Bandit problems have been studied in statistics, engineering, and psychology. In statistics, bandit problems fall under the heading “sequential design of experiments,” introduced by Thomp- son (1933, 1934) and Robbins (1952), and studied by Bellman (1956).

Greedy这个词在启发式搜索中很常用。

The term greedy is often used in the heuristic search literature (e.g., Pearl, 1984).

Optimistic initialization was used in reinforcement learning by Sutton (1996).