Skip to content

Instantly share code, notes, and snippets.

@awjuliani
Created September 11, 2016 00:20
Show Gist options
  • Save awjuliani/902fe41c3a9efe27299e72aee1b3158c to your computer and use it in GitHub Desktop.
Save awjuliani/902fe41c3a9efe27299e72aee1b3158c to your computer and use it in GitHub Desktop.
Policy gradient method for solving n-armed bandit problems.
Display the source blob
Display the rendered blob
Raw
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
@fredthedead
Copy link

The lower the bandit number, the more likely a positive reward will be returned

vs.

Currently bandit 4 (index#3) is set to most often provide a positive reward.

Shouldn't the first line be the opposite? the higher the bandit number the more likely a positive reward will be returned?

@jackleekopij
Copy link

A great tutorial!

I understand this is an introductory tutorial, however, I have found it an interesting outcome finding boundary conditions by playing with the reward probabilities (bandits) used in the pullBandits reward function along with the epsilon greedy parameter. Tweaking these parameters and observing the most promising bandit proved a great exercise for myself to understand sensitivities of the algorithm.

This for the post awjuliani

@bahriddin
Copy link

I tried with this details:

bandits = [-0.9, 0, -0.2, -1]
total_episodes = 100000
learning_rate=.01/total_episodes

But still, it can't find the global optimum. Are there any suggestions to improve algorithm?
Regards!

@JaeDukSeo
Copy link

One of the reason why this example might be confusing is due to the fact that tf can only minimize when performing auto differentiation. Thats that why the prob is flipped -5 being the best prop.

@JaeDukSeo
Copy link

@bahriddin that is due to the first selection choice, remember we initialize all of the weight to be one hence the argmax is 0. And since e is 0.1 small number we are not gonna explore that much, hence the agent will most likely choose the first one always and be wrong. If you increase the e value than it will be good.

@dhl8282
Copy link

dhl8282 commented Jul 10, 2018

@fredthedead

About

#List out our bandits. Currently bandit 4 (index#3) is set to most often provide a positive reward.
bandits = [0.2,0,-0.2,-5]

pullBandit method is defined as

def pullBandit(bandit):
#Get a random number.
result = np.random.randn(1)
if result > bandit:
#return a positive reward.
return 1
else:
#return a negative reward.
return -1

if you look carefully, result gives you a random positive or negative number.
Since bandits[3] = -5 which is more generous offset than bandits[1]=0, bandits[3] gives best chance.
Try this code and you will get is
for i in range(100): print np.random.randn(1)

@mapa17
Copy link

mapa17 commented Sep 1, 2018

Hi,

I have troubles to understand how the optimizer can tune the weights variable.

To my understanding the Optimizer will try to minimize (target loss=0.0) the loss function, but in the example above the weights start
out at 1.0, causing the initial loss value to be already 0.0.

loss = -(log(weight) * reward) = - (0.0 * reward) = - 0.0

weights = tf.Variable(tf.ones([num_bandits]))
...
responsible_weight = tf.slice(weights,action_holder,[1])
loss = -(tf.log(responsible_weight)*reward_holder)
optimizer = tf.train.GradientDescentOptimizer(learning_rate=0.001)

What do I miss or get wrong?

thx,
Manuel

@wzzhu
Copy link

wzzhu commented Oct 29, 2019

To my understanding the Optimizer will try to minimize (target loss=0.0) the loss function, but in the example above the weights start
out at 1.0, causing the initial loss value to be already 0.0.

loss = -(log(weight) * reward) = - (0.0 * reward) = - 0.0

What do I miss or get wrong?

f(x) = 0 doesn't mean f'(0) = 0, as long as the gradient of loss is not 0, eventually the weights will change.

In the example, as gradient(loss) = gradient(-log(weight)*reward)) = - reward * 1/weight (since d[lnx, x] = 1/x) and reward is const)
so gradient(loss) for (1) = -reward * 1/1 = -reward.

if reward == 1 (positive feedback), gradient = -1, so by gradient descend, it will subtract learning_rate * gradient, which is equivalent to adding learning_rate 0.001, so the new weight will become 1.001, giving it a little higher chance to be selected by argmax(weights). And so on.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment