I have two questions regarding the upper confidence bounds (UCB) exploration in reinforcement learning:

  1. UCB exploration is derived from Hoeffding's inequality which assumes that the reward is bounded in the interval [0,1]. If the rewards are not bounded in the interval [0,1] and we do not know the min and max reward in order to normalize them in [0,1] how UCB is applied?

  2. The original paper of UCB from Auer et al. 2002 is applied in multi-armed bandit setting where the rewards are iid variables. How can we apply the UCB in the MDP setting where we need an upper confidence bound for Q(s,a)?


1 Answer 1

  1. A popular hypothesis is that noise is subgaussian, which is broader than bounded variable (it includes gaussians) and for which we also have hoeffding inequality. Yet, there is still a parameter which is the analogue of the the length of the interval for bounded variables and quantifies the level of noise. If you dont know it beforehand, you can tune it by measuring the empirical variance. This algorithm is called UCB-V.

  2. There is an RL adaptation of UCB1, namely UCRL. It is optimistic on the reward and on the transition probabilities. This algorithm has strong theoretical background but is not very practical. Being optimistic on the transition probabilities means selecting a transition model in the confidence region which maximizes the cumulative reward. It is computationally expensive. Exploration in practical algorithm is often done by being optimistic solely on the state-action reward function.

Some materials about Exploration in RL 1 and DRL.

  • $\begingroup$ Thank you very much. The links you posted are very helpful $\endgroup$
    – gnikol
    Mar 13, 2020 at 23:49

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.