нелогичных результаты на несколько вооруженных бандита упражнений

Question

я работаю через главу 2, раздел 7, Саттон & Барт в подкрепление: Введение, которая занимается градиентными методами в нескольких вооруженных бандите проблеме. (Я понимаю, что второе издание представляет собой черновик, и кажется, что разделы немного перемещаются, но мой файл имеет раздел 2.7 под названием «Градиентные бандиты».) Мне удалось использовать методы в разделах 2.3-2.5 без проблем, но я постоянно получаю результаты с использованием методов градиента, которые сбивают с толку. Я пройду через свой код и покажу пример.

Просто инициализирует все здесь:

import random 
import math 
import numpy as np, numpy.random 

# number of arms (k) and step-size (alpha) 
k = 10 
alpha = 0.1 

# initialize preference function (H), and reward distribution (R) 
H = {i: 0 for i in range(k)} 
R = {i: [random.uniform(-100,100), 1] for i in range(k)} 

Я использую стационарные распределения вознаграждения, и я использую словари для представления этих распределений. Я предполагаю, что каждый награду описывается гауссовой, поэтому я отображение действия для поощрений с помощью следующей функции:

def getReward(action, rewardDistribution): 
    return random.gauss(rewardDistribution[action][0], rewardDistribution[action][1]) 

так называемая «функция предпочтения» H, который используется для определения вероятности действий, является также дается в словаре. Я распространяю выбор в очень широком диапазоне, так как каждая награда описывается распределением Гаусса со стандартным отклонением 1, расположенным где-то между -100 и 100. Я делаю это потому, что моя интуиция говорит мне, что это усложнит алгоритм, чтобы опираться на субоптимальный выбор, но я нахожу, что происходит противоположное.

Этот код выбирает свои действия на каждой итерации:

def selectAction(policy): 
    return np.random.choice(list(policy.keys()), p=list(policy.values())) 

И следующий код, который запускает итерации алгоритма. Обратите внимание, что pi является политикой и инициализируется, чтобы дать каждому событию вероятность 1/k.

avgReward = 0 
for i in range(100000): 
    pi = {i: math.exp(H[i])/sum([math.exp(H[j]) for j in range(k)]) for i in range(k)} 
    A = selectAction(pi) 
    R_A = getReward(A, R) 
    avgReward += (R_A - avgReward)/(i + 1) 
    H = {i: H[i] + alpha*(R_A - avgReward)*((i == A) - pi[i]) for i in range(k)} 

Уведомление Я выполняю 100 000 итераций, что для меня кажется, что это должно быть излишним. Это моя первая попытка решить эту проблему, поэтому моя интуиция может быть отключена, но я попытался настроить это, чтобы алгоритм нашел оптимальный выбор. Таким образом, я ожидаю, что процесс сходится к действию с распределением, имеющим наивысшее ожидаемое значение, и будет продолжать ударять его по мере продолжения итераций. Но, когда я распечатать результаты относительно каждого возможного действия со стороны бандита, это то, что я вижу:

for i in range(k): 
    print("Expected reward: " + str(R[i][0]) + " | Selection probability: " + str(pi[i]) + " | Preference: " + str(H[i])) 

Expected reward: -50.62506110888989 | Selection probability: 3.617077909489526e-13 | Preference: -7.82992533515 
Expected reward: 11.866419726345484 | Selection probability: 1.2337498052271344e-10 | Preference: -1.99777839484 
Expected reward: 75.41139657867947 | Selection probability: 1.5933517476231946e-09 | Preference: 0.560588358966 
Expected reward: -72.44467653824414 | Selection probability: 3.4267025247257986e-13 | Preference: -7.88399339198 
Expected reward: -43.466561447399 | Selection probability: 1.5933517476231946e-09 | Preference: 0.560588358966 
Expected reward: -75.99171566420297 | Selection probability: 1.5933517476231946e-09 | Preference: 0.560588358966 
Expected reward: -82.11920932060593 | Selection probability: 3.120658098513757e-13 | Preference: -7.97754791911 
Expected reward: 95.00643386364632 | Selection probability: 1.5933517476231946e-09 | Preference: 0.560588358966 
Expected reward: 31.384022070017835 | Selection probability: 1.2605442916195123e-08 | Preference: 2.62887724114 
Expected reward: 49.83925652065625 | Selection probability: 0.9999999808967586 | Preference: 20.8180143641 

Последнее действие имеет ожидаемую награду 49,8, и бандит выбирает его практически каждый раз. Это 3-й из лучших 10 вариантов, но он игнорирует опцию с ожидаемым вознаграждением 75.4 и еще один, который имеет ожидаемое вознаграждение 95.0.

Итак, мой вопрос: почему этот бандит не имеет оптимального выбора? Это всего лишь пример, это происходит довольно последовательно, когда я запускаю программу. Является ли моя интуиция относительно того, что я должен ожидать от бандита, или я неправильно кодировал этот алгоритм?

Answer 1

Проблема заключается в том, что многие руки (или действия, я использую оружие, поскольку это самая распространенная терминология в задачах MAB), не воспроизводятся даже в течение одного времени с вашей текущей настройкой. Вы можете легко убедиться, что это так, печатая для каждой руки, как часто она была выбрана.

Это происходит потому, что вы получаете довольно высокую абсолютную ценность. В литературе по проблемам МАБ они часто принимают награды в [0, 1] или [-1, 1]. Это не является строго необходимым (хотя для некоторых доказательств, связанных с теоретической эффективностью алгоритмов ... но это, вероятно, сейчас не интересно для вас). Во всяком случае, есть несколько способов устранить проблему:

1) Инициализировать список предпочтений (H) до больших значений, а не 0s. Это похоже на оптимистическую инициализацию epsilon-greedy, которая описана ранее в книге, поскольку она мотивирует алгоритм делать немного больше исследований ранее.

2) Резко уменьшить стоимость обучения alpha. Попробуйте что-то большее, как 0.00001, а не 0.1. Эффект этого изменения заключается в том, что значения предпочтений в H растут от 0 с меньшей скоростью, поэтому вероятности в pi также растут от начального 1/k с уменьшенной скоростью.

3) Повторно масштабируйте значения вознаграждения, которые должны находиться, например, [-1, 1] (для этого также потребуется соответствующее уменьшение стандартного отклонения распределений вознаграждений, если вы не хотите проблемы чтобы стать более сложным.