Bellman rank

With function approximation, some RL problems are learnable from a modest amount of data and others are hopeless, and on the surface it is hard to tell which is which. Bellman rank is a complexity measure invented to draw that line. Intuitively it captures how much genuinely new information each new policy reveals about the Bellman errors of all the others — if that information lives in a low-dimensional space, exploration cannot keep surprising you forever.

Formally one arranges the average Bellman errors of policy i's value estimate, evaluated under policy j, into a matrix, and the Bellman rank is the rank of that matrix. A small rank means a low-dimensional structure ties all the candidate value functions together, and algorithms like OLIVE then learn a near-optimal policy with sample complexity polynomial in that rank, the horizon, and log of the function-class size — not in the number of states. Linear MDPs and several other tractable models all have low Bellman rank.

Low Bellman rank is sufficient for sample-efficient learning but not always computationally efficient, and it is only one of several competing complexity measures (Bellman-Eluder dimension, the Decision-Estimation Coefficient) that researchers still argue over for the cleanest characterization of when general function approximation is learnable.