Multi-Armed Bandit - Reward Probabilities

Question

I am new to reinforcement learning, and recently came across the following issue. When implementing a multi-armed bandit algorithm, we assume we have k machines with reward probabilities [p_1,..., p_k] which we try to approximate. While these probabilities are clearly unknown to the player himself, they must still be encoded in the algorithm in the sense that we have to specify:

""" return 1 with the arm's predefined probability """

    if np.random.random() < self.p:
       return 1
    else:
       return 0

My question is how we can set those predefined probabilities (e.g. for ad optimisation).

Answer 1

As pointed out by @D.W. you are not required to hardcode these probabilities in the algorithm to obtain an optimal strategy, but you do need to know them if you want to model the scenario.

A big step towards optimal solutions to the Multi-Armed Bandit problem (where a player doesn't know the underlying probability distribution of rewards) was given in 1996 by Burnetas and Katehakis in their paper "Optimal adaptive policies for sequential allocation problems". In particular they include the case in which the distributions of outcomes depend on unknown parameters (see section Optimal solutions in the Wikipedia page of Multi-armed bandit for example).

Thompson's sampling allows to do this in a simple way following the steps described here. Initially you assume a prior $P(\theta)$ and then update it into your posterior $P(\theta|\{a,x,r\})$, as you get more information after every action. An action $a^*$ is then chosen, each with probability

$$ \mathbb{P}(a^*) = \int_{\Theta} \mathbb{1}_{[\mathbb{E}(r|a^*,x,\theta)\ =\ \max_{a}\mathbb{E}(r|a,x,\theta )]}P(\theta|\{a,x,r\})d\theta. $$

Of course, if $a^*$ maximises the reward under the assumed parameters then it's chosen with probability 1. Eventually we hope for $P(\theta|\{a,x,r\})$ to converge to the underlying true (unknown) distribution of parameters. Notice that to choose an action in practice, sampling techniques are usually implemented.

Going back to the initial comment on modelling the scenario, if you want to code a game to test Thompson's algorithm, then the ``casino'' must give a reward on every round after an action is chosen and this reward is indeed the true one, so you must input the hidden distribution. This will still not be seen by the player applying the algorithm. In the case of add placement, the underlying true distribution is inherent to the user while the company placing the add wishes to obtain the highest reward.

Answer 2

Thompson sampling doesn't require knowing the true success probability of each arm. I'm not clear on why you suggest it does. Quite to the contrary, it computes an integral over all possibilities for what that probability could be (or, it estimates this integral by sampling from the distribution over such probabilities).

Responding to the revised question: The question contains an incorrect claim. Thompson sampling does not require hardcoding those probabilities in the algorithm. I am not sure where you obtained that code from or what the variables are intended to represent, so it is hard to comment on that specific code.