The authors consider adversarial linear MDPs where the learner observes only bandit feedback (the loss of the chosen action) and, in the harder variant, only the aggregate episode loss rather than per-step losses.
Polynomial-time algorithm achieves optimal regret for adversarial linear MDPs
The authors close the gap between computational efficiency and rate-optimality by reducing adversarial linear MDPs to linear bandits with an approximate separation oracle.
Academic
Haolin Liu · Chen-Yu Wei · Hanbin Zhou
University of Virginia · Hong Kong University of Science and Technology
Research Digest··3 min read
Liu, Wei, and Zhou study episodic linear Markov decision processes with unknown transitions, adversarial losses, and bandit feedback.
§