  Model-free algorithms for reinforcement learning typically require a
condition called Bellman completeness in order to successfully operate
off-policy with function approximation, unless additional conditions are met.
However, Bellman completeness is a requirement that is much stronger than
realizability and that is deemed to be too strong to hold in practice. In this
work, we relax this structural assumption and analyze the statistical
complexity of off-policy reinforcement learning when only realizability holds
for the prescribed function class.
  We establish finite-sample guarantees for off-policy reinforcement learning
that are free of the approximation error term known as inherent Bellman error,
and that depend on the interplay of three factors. The first two are well
known: they are the metric entropy of the function class and the
concentrability coefficient that represents the cost of learning off-policy.
The third factor is new, and it measures the violation of Bellman completeness,
namely the mis-alignment between the chosen function class and its image
through the Bellman operator.
  In essence, these error bounds establish that off-policy reinforcement
learning remains statistically viable even in absence of Bellman completeness,
and characterize the intermediate situation between the favorable Bellman
complete setting and the worst-case scenario where exponential lower bounds are
in force. Our analysis directly applies to the solution found by temporal
difference algorithms when they converge.
