I am trying to model a sequential exploration-exploitation problem with learning as a multi-armed bandit, where the reward mixes a Markovian and a stochastic reward.

I understand how to model a bandit problem with Markovian rewards. In a Markovian bandit problem, each time the Decision Maker (DM) pulls an arm, the state of the arm changes according to a Markov chain and it obtains the reward associated with the transition. One way to solve this kind of problem is the Gittins index.

On the other hand, I also know different ways to solve a bandit problem with stochastic rewards. In a stochastic reward bandit problem, each time the DM pulls an arm, it obtains a reward drawn from a known distribution, whose parameters are unknown and the DM tries to learn. There are several index policies and inference models to apply (UCB, Knowledge Gradient, etc.).

But what if the reward mixes both concepts? That is, each time the DM pulls an arm, it obtains a reward which has a factor that is dependent on a state transition, but at the same time, other factor of the reward is drawn from a known distribution (with unknown parameters), common to all states of the Markov chain?

To clear things up: the reward is something like A_st*X, where "A_st" depends on the state (to make things easier, we could consider it is deterministic given a state), and "X" ~ N(mu, sigma), common to all states?

The only model I can come up with would rely on integrating my belief about "X" into the state space and then trying to compute the Gittins index through some sort of ADP (which may not be possible).

Bonus round: is it possible to go even further and formulate this as a superprocess? (instead of a Markov chain, having an MDP?).

EDIT tl;dr:

How do you deal with a multi-armed bandit problem in which the reward is NOT in the form of the typical conjugate distributions (like the exponential-gamma learning model)?

  • $\begingroup$ A super late response: isn't this just reinforcement learning? The reward depends on the state and action, and the next state depends on the state and action. Also see this blog that have some clear pictures about the relation between RL and MAB. $\endgroup$
    – Pieter
    Commented Jun 20, 2018 at 19:17

1 Answer 1


Wow, super super late coming back here. I just wanted to leave here that this question led to a published paper. Not having an answer was quite a good hint :)



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.