Information-Theoretic Considerations in Batch Reinforcement Learning
Jinglin Chen (UIUC), Nan Jiang (UIUC)

Introduction

On Concentratability

On Inherent Bellman Error● Batch value-func approx (≈ADP): backbone of many deep RL alg○ e.g., FQI --- DQN● Prior works prove that they work under certain assumptions [1]● Are they necessary? Do they hold in interesting scenarios?
○ We seek info-theoretic (alg-independent) hardness to justify necessity

Exponential lower bound when C is unbounded● Known & dtmn dynamics, unknown reward● F realizes Q★ for every possible MDP● Similarly G => no inherent Bellman error● No eﬃcient exploration algorithm exists● Any data distribution + any batch alg= special case of exploration algorithm

Conjecture There exists a family of MDPs 𝓜, such that: any algorithmwith realizable F as input cannot have poly(log|F|, H, C) complexity.

Setting and Algorithms

Fitted Q-Iteration [2]: Initialize f0 ∈ Fft = solution to regression problem {(s, a) -> r + 𝛾 maxa’ ft-1(s’, a’)} over F● C measures how exploratory the data is● More than that! If MDP dynamics areunregulated, no distribution works!
.

Modiﬁed Bellman Residual Minimization [1]argminf supg LD(f; f) - LD(g; f),where LD(f; f’) := ∑(s,a,r,s’) [f(s, a) - r - 𝛾 maxa’ f’ (s’, a’)]2

Assumptions and Upper bounds
Data dist.

Data Assumptions● Data distribution well covers states(and actions) visited by any policy π● Measured by C: worst-case (overstate & policy) density ratio

F“Value-proﬁle” idea doesn’t work in tabular constructions● Hide info of s and only reveal {f (s,a): f ∈ F, a ∈ A} [4, 5]● Issue with construction in [5]: not realizable● When realizable: eﬃcient learning exists using Q*-irrelevant abstraction

Example of “smooth dynamics”(𝒯 f)(s, a) = R(s, a) + 𝛾 Es’|s, a[maxa’ f (s’, a’)]H = 1/(1-𝛾)Dist. inducedby any π● High-dimensional observations generated
from ﬁnite & small hidden state space● Same as environments that allow
sample-eﬃcient exploration [3]● Can construct small C by taking mixture ofdistributions of several policies

Why care?
● If true, construction is seriously stochastic and “non-bandit”● All known RL lower bound are nearly deterministic andbandit-structured --- no reﬂection of the long-horizon challenge of RL

High-level implications
Online (exploration)

Batch

Left: Dann & Brunskill’15
Right: Osband & Van Roy’16

smallfF

Π𝐹 𝒯 fUpper bounds● Under above assumptions, poly(log|F|, C, H) sample complexity [1]● We provide simpliﬁed analyses under minimal setup○ Error rate for modiﬁed BRM [1] improved n-1/4 → n-1/2

Smooth dynamics+ exploratory data+ Realizability + ???
Gap?

𝒯f

Value-based

State-action space“Concentratability Coeﬃcient”
Representation Assumptions● Realizability: Q★ ∈ F● Need more! supf || Π𝐹 𝒯 f - 𝒯 f || ≈ 0(or: G => supf infg || g - 𝒯 f || ≈ 0)“Inherent Bellman error”

Construct an exponential-sized model family => fail!
Reason: Batch model-based RL only needs realizability● Create “small” (F, G) from 𝓜 : realizable & no inherent Bellman error
Lesson: Need to rule out model-based algorithms.

● What kind of problems have “smooth dynamics”?

Model-based

Bellman update :Eﬀective horizon :Obvious? Info-theoretic lower bound?

Implication

Setting: learn near-optimal policy from data {(s, a, r, s’)} + function class F● (s, a) is drawn i.i.d. from “data distribution”

Notations

Why should be true:● No poly alg known under general func approx with realizability alone● Divergence of ADP known for decades

Smooth dynamics+ exploratory data+ Realizability

Gap?

Smooth dynamics(low Bellman rank [2])+ Realizability
Gapexists
Smooth dynamics(low witness rank [3])+ Realizability● May shed light on related questions○ “True” horizon dependence in RL (JA18, COLT open problem)○ Exploration with linear function approximation
Connection to State Abstractions
𝜙 is bisimulation ⟺ F𝜙 (piece-wise constant) has 0 inherent Bellman error● ⇒ is trivial● ⇐:○ Use f = 0 to witness reward errors.
○ Use f as the argmax of <P(s1, a) - P(s2, a), f > for any aggregated s1 ands2 to witness transition errors.

References[1] Antos, A., Szepesvári, C., and Munos, R. Learning near-optimal policies with bellman-residual minimization based ﬁtted policy iteration and a single sample path. Machine Learning, 71(1):89–129, 2008.
[2] Ernst, D., Geurts, P., and Wehenkel, L. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6:503–556, 2005.
[3] Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. Contextual Decision Processes with low Bellman rank are PAC-learnable. In International Conference on Machine Learning, 2017.
[4] Sun, W., Jiang, N., Krishnamurthy, A., Agarwal, A., and Langford, J. Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches. In Conference on Learning Theory, 2019.
[5] Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018.