A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Setting
By P. Amortila, Nan Jiang, Tengyang Xie. 2020
29 citations recorded by the source corpus.
Recently, Wang et al. (2020) showed a highly intriguing hardness result for batch reinforcement learning (RL) with linearly realizable value function and good feature coverage in the finite-horizon case. In this note we show that once adapted to the discounted setting, the construction can be simplified to a 2-state MDP with 1-dimensional features, such that learning is impossible even with an infinite amount of data.
Subfields: Artificial Intelligence, Management Science and Operations Research
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Management Science and Operations Research
Citations in the corpus
- Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL (2020, background): “…the form of the above lower bound with that of some concurrent results for the off-policy evaluation problem: for example, (Wang et al., 2020a; Amortila et al., 2020) show that there exist a sampling distribution µ (that induces the best-conditioned covariance matrix), a target policy π and…”