What algorithms are known to work well with contextual, non-stationary, infinite armed bandits?

In case it isn't clear:

  • Contextual: I mean that the rewards depend, not only on our actions, but state (e.g. a feature vector) as well.
  • Non-stationary Rewards $R$ are also a function of time, i.e. $R(s,a,t)$
  • Infinitely-many arms: A subset of the arms live in $\rm I\!{R}^d$ (e.g. say $d$ arms live in $\rm I\!{R}$, i.e. a continuum).

Bayesian optimization methods are particularly relevant here, but, if I understand correctly, most solutions I have seen don't consider state or non-stationarity .

When it comes to factoring in state, one thought I had to was to include it as part of the data on which we condition the posterior. That is, the Gaussian Process kernel would specify covariance not only on dimensions of the arms, but also on the state, even if the state is always known (but varying of course).

Would doing the latter make sense? If so, what's the advice on these types of kernels? Any other way to accommodate state?

Also, how do we accommodate non-stationarity in the model? Perhaps using an exponential kernel to model time? If we go down this route, how does one combine all these kernels into a single GP?

  • $\begingroup$ Could you make it more specific what do you mean by "continuum armed bandits"? What are the arms in this scenario? $\endgroup$
    – Tim
    Nov 5, 2016 at 20:46
  • $\begingroup$ Thanks @Tim I updated the OP. Let me know if it isn't still clear. $\endgroup$ Nov 5, 2016 at 21:07

1 Answer 1


Not a complete answer, but more of a 'too big for comments' pointer:

I'd start by looking for generalisations of Bayesian nonparametric hidden markov models combined with markov decision processes.

Here's a paper I found using that as the base for a search: 'The Infinite Partially Observable Markov Decision Process' (NIPS '09). I've not read it carefully, but there appear to be some interesting references for other elements of your question (non-stationarity, finite case algorithms).

On non-stationarity, and take this with a pinch of salt, but Dirichlet Process based models can fit very complex data, to the extent where you might find that sets of states are active for finite stretches of your time series (i.e. achieve non-stationarity, possibly at the price of complexity).

  • $\begingroup$ I see, thanks. I am guessing the Dirichlet process helps identify/cluster states (i.e. their transitions)? $\endgroup$ Nov 7, 2016 at 20:21
  • 1
    $\begingroup$ IIRC with infinite HMMs the DP provides the model for an infinite number of hidden states. Each state indexes an observation distribution, which generate the data you see at each time point. I expect they've worked to integrate the action and reward aspects into the transitions. $\endgroup$ Nov 7, 2016 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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