Learning Near Optimal Policies with Low Inherent Bellman Error

Understand

We study the exploration problem with approximate linear action-value functions in episodic reinforcement learning under the notion of low inherent Bellman error, a condition normally employed to show convergence of approximate value iteration.

• First we relate this condition to other common frameworks and show that it is strictly more general than the low rank (or linear) MDP assumption of prior work.
• Second we provide an algorithm with a high probability regret bound $\widetilde O(\sum_{t=1}^H d_t \sqrt{K} + \sum_{t=1}^H \sqrt{d_t} \IBE K)$ where $H$ is the horizon, $K$ is the number of episodes, $\IBE$ is the value if the inherent Bellman error and $d_t$ is the feature dimension at timestep $t$.
• In addition, we show that the result is unimprovable beyond constants and logs by showing a matching lower bound.