Piecewise-Stationary Bandit Problems with Side Observations

author: Jia Yuan Yu, Electrical and Computer Engineering Department, McGill University
published: Aug. 26, 2009,   recorded: June 2009,   views: 2814


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


We consider a sequential decision problem where the rewards are generated by a piecewise-stationary distribution. However, the different reward distributions are unknown and may change at unknown instants. Our approach uses a limited number of side observations on past rewards, but does not require prior knowledge of the frequency of changes. In spite of the adversarial nature of the reward process, we provide an algorithm whose regret, with respect to the baseline with perfect knowledge of the distributions and the changes, is O(k \log(T), where k is the number of changes up to time T. This is in contrast to the case where side observations are not available, and where the regret is at least Omega(sqrt{T}).

See Also:

Download slides icon Download slides: icml09_yu_psbp_01.pdf (265.9┬áKB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: