EXP4 algorithm for contextual bandits: where do experts come from?

Question

I am working on an implementation of the EXP4 algorithm in the context of a pricing decision (e.g. given a context, the user should be given a price from a few pre-determined options).

The EXP4 uses "experts" as a mean to handle various aspects of the context. however, all the papers I've read where silent about where do these experts come from? how one decide how many experts are needed? how one trains these experts? are these experts get updated over time as a result of decisions and reward or only the MAB who evaluate and average across all these experts?

I'd appreciate any reference with either an example or a more detailed discussion on "where do expert come from" in the context of contextual bandits.

Thanks.

Answer 1

I'm not a bandits expert but here is my understanding. I'll answer your question in parts:

Q: Where do these experts come from?
A: The experts are defined in contextual bandits papers to be very general, allowing for flexibility in the sorts of problems to which they can be applied. Thus, your experts may be inspired by the problem at hand. Take as an example trying to price health insurance given a patient's context (their age, pre-existing health conditions, lifestyle, etc). You may create an "expert" for each of these individual aspects of the context. Such experts can be dead simple, using hand specified thresholds for making recommendations. E.g the "age" expert could simply recommend one price for persons under 40 and another for persons above. They could be more complex learned models trained on some data. A common approach is to partition the arm and/or context space somehow and assign a single expert to each partition. The expert can then randomly recommend an arm from its assigned partition, hoping to exploit some similarity between arms and contexts within its partition.

Q: How does one decide how many experts are needed?
A: Again, this is problem specific. However, there is a sort of inverse relationship between the number of experts and number of arms allowed to achieve a reasonable regret. From [1]:

... the price paid for adding experts is relatively low, as long as we have few actions ... the number of actions can be very high, yet the regret will be low if we have only a few experts.

In other words, if you have a lower number of arms, you can have a higher number of experts, and vice-versa.

Q: How does one train these experts?
A: As discussed above, training may not be necessary at all depending on your experts. They can be very simple, or they can be trained on labeled context examples ahead of time if they are available.

Q: Are the experts updated over time?
A: I believe the experts are typically assumed to be static while the bandit algorithm is training, at least for the sake of regret analysis. There may be formulations with which I am unfamiliar that allow experts to learn during the bandit training.

References:
1: http://banditalgs.com/2016/10/14/exp4/
2: https://arxiv.org/pdf/1508.03326.pdf
3: http://proceedings.mlr.press/v19/slivkins11a/slivkins11a.pdf