Обучение с подкреплением

Введение

Многорукий бандит — это простейшая постановка sequential decision making без состояний. У нас есть множество ручек $\mathcal{A}=\{ a_{1}, \dots, a_{n} \}$ и неизвестное распределение награды для каждой из ручек: $r_{t} \sim p_{a}$. На каждом шаге агент выбирает действие $a_t \in \mathcal{A}$ и получает за него стохастическую награду. В стационарной постановке распределение каждой ручки не меняется со временем, а раунды независимы друг от друга.

Несмотря на простую постановку, здесь уже есть дилемма exploration vs exploitation, но ещё нет состояний, переходной динамики и отложенных последствий действий. Цель агента за горизонт $T$ — выбрать последовательность ручек $a_{1},\dots,a_{T}\in \mathcal{A}$, которая бы максимизировала ожидаемую суммарную награду

$$\mathbb{E}\left[ \sum_{t}^{T}r_{t} \right]$$

Чтобы это сделать, нужно как-то оценить качество выбранной ручки, для этого введем истинную ценность ручки $q(a)$ следующим образом

$$q(a)=\mathbb{E}[r_{t}\mid a_{t}=a],\quad r_{t}\sim p_{a_{t}}$$

Если бы истинные значения $q(a)$ были известны (но мы их не знаем, так как распределение $p_{a_{t}}$ наград $r_{t}$ не известны), мы бы всегда выбирали оптимальную ручку

$$a^* \in \arg\max_{a \in \mathcal{A}} q(a).$$

И тем самым бы определили политику $\pi: \tau_{t}\to \mathcal{A}$, где $\tau_{t}=(a_{1},r_{1},a_{2},\dots)$ — траектория выборов агента и соотвествующих наград (просто история действий агента), на каждом шаге выбираея ручку с максимальной наградой.

Но все же можно строить эмпирические оценки фукнции ценности, будем называть ее эмпирической ценность ручки

$$\hat{q}_{t}(a)=\frac{1}{N_{t}(a)}\sum_{s\leq t:\ a_{s}=a} r_{s}=\frac{1}{N_{t}(a)} \sum_{s=1}^{T} r_{s}\cdot \mathbb{1}{\{ a_{t}=a \}},$$

где $N_{T}(a)$ — количество раз, когда агент выбрал действие $a$ за $T$ шагов.

Каждая такая оценка истинной фукнции ценности индуцирует какую-то политику $\pi$ и было бы не плохо понять, как можно оценивать и сравнивать успешность той или иной политики. В качестве метрики качества удобно смотреть на награду, потерянную по сравнению с такой всезнающей политикой (ее еще называют оракулом). Эта величина называется cumulative regret:

$$\mathrm{Regret}(T)= \sum_{t=1}^T\left( \max_{a\in \mathcal{A}}q(a) - \hat{q}(a_{t}) \right)$$

Если обозначить разрыв субоптимальности как $\Delta_a = \max_{b \in \mathcal{A}} q(b) - \hat{q}(a)$ и число выборов действия $a$ как $N_T(a)$, то

$$\mathbb{E}[\mathrm{Regret}(T)] = \sum_{a \in \mathcal{A}} \Delta_a \, \mathbb{E}[N_T(a)].$$

Это важное разложение: минимизировать regret означает как можно реже выбирать субоптимальные действия.

Вернемся к эмпирической оценке фукнции ценности ручки. Пусть на шаге $t+1$ агент выбрал ручку $a$, тогда

$$q_{t+1}(a)=\frac{1}{N_{t+1}(a)}\sum_{s=1}^{t+1}r_{s}\cdot \mathbb{1}\{ a_{s}=a \}=\frac{1}{N_{t+1}(a)}\left( N_{t}(a)q_{t}(a)+r_{t+1} \right) =$$ $$\frac{N_{t}(a)+1-1}{N_{t+1}(a)} q_{t}(a) +\frac{r_{t+1}}{N_{t+1}(a)}=q_{t}(a)+\frac{1}{N_{t+1}(a)}\left( r_{t+1}-q_{t}(a) \right)$$

Мы получили инкрементальную формулу обновления фукнции ценности, то есть больше нет необходимости хранить всю историю действий, теперь для обновления достаточно одно только $q(a)$. Можно записать эту формулу в более общем виде

$$q\leftarrow q+\alpha(r-q)$$

Если взять $\alpha = 1 / N_t(a)$, получаем выборочное среднее. Если задача нестационарна и распределения награды со временем дрейфуют, часто лучше брать постоянный шаг $\alpha \in (0,1)$: тогда старые наблюдения экспоненциально забываются.

в теории стохастической оптимизации сущесвуют условия, налагающие ограничения на $\alpha$: чтобы процесс оценки среднего $q_{t}(a)\to q(a)$ сходился почти наверное, нужны условия:

$$\sum_{t}^{\infty}\alpha_{t}=\infty,\quad \sum_{t=1}^{\infty}\alpha_{t}^2<\infty$$

Теперь зададимся вопросом получения политики из сущесвующей фукнции ценности

ε-greedy политика

Если на каждом шаге выбирать действие, максимизируеющее награду, мы не будем исследовать новые стратегии. Так если на ранних шагах значения наград дали выброс, то мы получим неправильную оценку, и алгоритм зафиксируется на плохом действии. Поэтому можно добавить элемент случайности и ввести $\varepsilon$-жадную политику:

$$A_{t}=\begin{cases} \arg \max _{a\in \mathcal{A}}Q_{t}(a), & p=1-\varepsilon, \\ \mathrm{Uniform}(\mathcal{A}), & p=\varepsilon. \end{cases}$$

При фиксированном $\varepsilon > 0$ такая стратегия продолжает случайно исследовать и на поздних шагах, поэтому её regret растёт линейно по $T$

UCB

Вместо добавления вероятности выбора случайного действия можно добавить бонус за неопределённость:

$$a_{t}=\arg\max_{a \in \mathcal{A}}\left( q_{t}(a)+\sqrt{ \frac{c\ln t}{N_{t}(a)} } \right).$$

Если действие мало пробовали, то за него будет большой бонус, что приводит к исследованию менее изученных действий. Баланс между exploration и exploitation сохраняется автоматически.

Эта стратегия называется Upper Confidence Bound. Идея в том, что мы выбираем не просто действие с наибольшей текущей средней наградой, а действие с наибольшей верхней доверительной границей. Если для некоторой ручки оценка неточная, то доверительный интервал широкий, и алгоритм будет чаще её исследовать.

Это пример принципа optimism in the face of uncertainty: если про действие мало известно, алгоритм временно предполагает для него более благоприятный сценарий и тем самым заставляет себя собрать информацию.

Для формального объяснения формулы нужно использовать неравенство Хёфдинга: Пусть $X_{1},\dots X_{n}$ — i.i.d. и $\forall i:\mathbb{P}(X_{i}\in[a_{i},b_{i}])$, тогда

$$\mathbb{P}(\overline{X}_{n}-\mathbb{E}[\overline{X}_{n}]\geq\varepsilon)\leq \exp \left( -\frac{2\varepsilon^2n^2}{\sum_{i=1}^n (b_{i}-a_{i})^2} \right)$$

В частности, если считать, что $r_{t}\in[0,1]$, то неравенство принимает вид

$$\mathbb{P}(\mid q_{t}(a)- \hat{q}_{t}(a) \mid \geq \varepsilon ) \leq 2\exp(-2n\varepsilon^2) \implies\varepsilon=\sqrt{ \frac{\ln(2/\delta)}{2n} }$$

Тогда соотвествующая политика будет имеет вид

$$a_t = \arg\max_{a \in \mathcal{A}}\left( Q_t(a) + \sqrt{\frac{c \ln t}{N_t(a)}} \right).$$

Интуитивно:

• первое слагаемое отвечает за exploitation, то есть выбор ручек с большой средней наградой;
• второе слагаемое отвечает за exploration, то есть за интерес к ручкам, которые ещё мало исследовали.

Замечание:

• в начале работы нужно хотя бы один раз попробовать каждое действие, иначе для $N_t(a)=0$ формула не определена;
• в классической постановке UCB1 при ограниченных наградах достигается логарифмический regret $O(\log T)$, то есть существенно лучше, чем у $\varepsilon$-жадной стратегии с фиксированным $\varepsilon$;
• UCB детерминирован после фиксации наблюдений: вся случайность связана только с наградами среды, а не с самой политикой.

Thompson Sampling

Ещё один популярный подход — Thompson Sampling. Его идея состоит в том, чтобы не подставлять в политику одну точечную оценку $q_t(a)$, а поддерживать распределение неопределённости на параметрах награды и сэмплировать из него.

Пусть у каждой ручки есть неизвестный параметр $\theta_a$. Тогда мы поддерживаем апостериорное распределение

$$p(\theta_a \mid \mathcal{D}_t),$$

где $\mathcal{D}_t$ — все наблюдения к моменту $t$. На шаге $t$:

1. для каждой ручки сэмплируем

$$\tilde{\theta}_a \sim p(\theta_a \mid \mathcal{D}_t);$$

2. выбираем действие

$$a_t= \arg\max_{a \in \mathcal{A}} \tilde{\theta}_a;$$

3. наблюдаем награду и обновляем posterior.

Интуитивно это тоже баланс exploration/exploitation:

• если по ручке уже много данных, posterior узкий, и сэмплы почти одинаковые;
• если данных мало, posterior широкий, и ручка иногда будет получать большие сэмплы, из-за чего её будут исследовать.

Удобная интерпретация: вероятность выбора действия примерно равна апостериорной вероятности того, что именно оно оптимально. Поэтому exploration здесь возникает не из внешнего шума и не из явного доверительного бонуса, а из самой байесовской неопределённости.