Poster
Online learning in episodic Markovian decision processes by relative entropy policy search
Alexander Zimin · Gergely Neu

Thu Dec 5th 07:00 -- 11:59 PM @ Harrah's Special Events Center, 2nd Floor #None
in Poster Session »
We study the problem of online learning in finite episodic Markov decision processes where the loss function is allowed to change between episodes. The natural performance measure in this learning problem is the regret defined as the difference between the total loss of the best stationary policy and the total loss suffered by the learner. We assume that the learner is given access to a finite action space $\A$ and the state space $\X$ has a layered structure with $L$ layers, so that state transitions are only possible between consecutive layers. We describe a variant of the recently proposed Relative Entropy Policy Search algorithm and show that its regret after $T$ episodes is $2\sqrt{L\nX\nA T\log(\nX\nA/L)}$ in the bandit setting and $2L\sqrt{T\log(\nX\nA/L)}$ in the full information setting. These guarantees largely improve previously known results under much milder assumptions and cannot be significantly improved under general assumptions.

Author Information

Alexander Zimin (Amazon)
Gergely Neu (Universitat Pompeu Fabra)

More from the Same Authors