  We study sample efficient reinforcement learning (RL) under the general
framework of interactive decision making, which includes Markov decision
process (MDP), partially observable Markov decision process (POMDP), and
predictive state representation (PSR) as special cases. Toward finding the
minimum assumption that empowers sample efficient learning, we propose a novel
complexity measure, generalized eluder coefficient (GEC), which characterizes
the fundamental tradeoff between exploration and exploitation in online
interactive decision making. In specific, GEC captures the hardness of
exploration by comparing the error of predicting the performance of the updated
policy with the in-sample training error evaluated on the historical data. We
show that RL problems with low GEC form a remarkably rich class, which subsumes
low Bellman eluder dimension problems, bilinear class, low witness rank
problems, PO-bilinear class, and generalized regular PSR, where generalized
regular PSR, a new tractable PSR class identified by us, includes nearly all
known tractable POMDPs and PSRs. Furthermore, in terms of algorithm design, we
propose a generic posterior sampling algorithm, which can be implemented in
both model-free and model-based fashion, under both fully observable and
partially observable settings. The proposed algorithm modifies the standard
posterior sampling algorithm in two aspects: (i) we use an optimistic prior
distribution that biases towards hypotheses with higher values and (ii) a
loglikelihood function is set to be the empirical loss evaluated on the
historical data, where the choice of loss function supports both model-free and
model-based learning. We prove that the proposed algorithm is sample efficient
by establishing a sublinear regret upper bound in terms of GEC. In summary, we
provide a new and unified understanding of both fully observable and partially
observable RL.
