  We consider the problem of reinforcement learning over episodes of a
finite-horizon deterministic 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 lies within a given hypothesis class, OCP selects optimal
actions over all but at most K episodes, where K is the eluder dimension of the
given hypothesis class. We establish further efficiency and asymptotic
performance guarantees that apply even if the true value function does not lie
in the given hypothesis class, for the special case where the hypothesis class
is the span of pre-specified indicator functions over disjoint sets. We also
discuss the computational complexity of OCP and present computational results
involving two illustrative examples.
