Considering a multi-armed bandit problem where there are :

C: number of machines
T: timesteps
m(i) , v(i) = mean and variance of i-th machine's reward distribution
A(i) = Selected Machine index at timestep i
R(i) = Received Reward at timestep i : ~ N(m(A(i)),v(A(i))

(all indexes start from 1)

If we decide to follow this policy:

  1. For steps i = 1 to C selecting machine i in other words A(i) = i for i <= C
  2. For steps i > C selecting machine which has the highest score (Z is score function) : Z(j, i , R(1 to i-1), A(1 to i-1)) where j is machine's index and i is timestep

So we would have our expectation for the total reward as : $$ \mathbb{E}[R_{total}] = \sum_{i=1}^T{\mathbb{E}[R(i)]} = \sum_{i=1}^C{m(i)} + \sum_{i=C+1}^T{\sum_{j=1}^C{m(j)*Pr(A(i) = j)}} $$ And also we have: $$ Pr(A(i) = j) = \prod_{k \neq j}{Pr( Z(\textbf{j}, i , R([1... i-1]), A([1... i-1])) >Z(\textbf{k}, i , R([1... i-1]), A([1...i-1])))} $$

so we have this objective of finding unknown function Z which maximizes $\mathbb{E}[R_{total}]$: $$ \DeclareMathOperator*{\argmax}{arg\,max} Z = \argmax_{Z()}{\mathbb{E}[R_{total}]} = \argmax_{Z}{\sum_{i=C+1}^T{\sum_{j=1}^C{m(j)*Pr(A(i) = j)}}} $$ (I purned out first term in $\mathbb{E}[R_{total}]$ since it is a constant)

I know there are well-known techniques like UCB, epsilon-greedy ,... however I think there should be an optimal Z function even if we dont have any information about mean and variance of reward distributions, because at least we know that they are normally distributed in this case.

My questions are :

  1. Is there any well known technique to solve such problems ? where we don't have any specific form for the function which we are trying to find ?
  2. Is my assumption correct about existence of an optimal Z function ?


You must log in to answer this question.