Efficient Exploration and Value Function Generalization in Deterministic Systems
Zheng Wen, Benjamin Van Roy · 2013
We consider the problem of reinforcement learning over episodes of a finite-horizon deter-ministic system and as a solution propose optimistic constraint propagation (OCP), an algorithm designed to synthesize efficient exploration and value function generalization. We establish that when the true value function Q ∗ lies within the hypothesis class Q, OCP selects optimal actions over all but at most dimE[Q] episodes, where dimE denotes the eluder dimension. We establish further efficiency and asymptotic performance guarantees that apply even if Q ∗ does not lie in Q, for the special case where Q is the span of pre-specified indicator functions over disjoint sets.