Comments on the Du-Kakade-Wang-Yang Lower Bounds

2019-11-18 · Benjamin Van Roy, Shi Dong

Du, Kakade, Wang, and Yang recently established intriguing lower bounds on sample complexity, which suggest that reinforcement learning with a misspecified representation is intractable. Another line of work, which centers around a statistic called the eluder dimension, establishes tractability of problems similar to those considered in the Du-Kakade-Wang-Yang paper. We compare these results and reconcile interpretations.

📄 PDF Abstract BibTeX arXiv:1911.07910

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Setting

2020-11-02 · Philip Amortila, Nan Jiang, Tengyang Xie

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 …

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Response to Discussions of "Causal and Counterfactual Views of Missing Data Models"

2025-10-16 · Razieh Nabi, Rohit Bhattacharya, Ilya Shpitser, James M. Robins arxiv

We are grateful to the discussants, Levis and Kennedy [2025], Luo and Geng [2025], Wang and van der Laan [2025], and Yang and Kim [2025], for their thoughtful comments on our paper (Nabi et al., 2025). In this rejoinder,…

Lower Bounds for Smooth Nonconvex Finite-Sum Optimization

2019-01-31 · Dongruo Zhou, Quanquan Gu

Smooth finite-sum optimization has been widely studied in both convex and nonconvex settings. However, existing lower bounds for finite-sum optimization are mostly limited to the setting where each component function is …

Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuron

2023-03-03 · Jingfeng Wu, Difan Zou, Zixiang Chen, Vladimir Braverman 외

This paper considers the problem of learning a single ReLU neuron with squared loss (a.k.a., ReLU regression) in the overparameterized regime, where the input dimension can exceed the number of samples. We analyze a Perc…

regression Vocal Bursts Intensity Prediction

Logistic Regression Regret: What's the Catch?

2020-02-07 · Gil I. Shamir

We address the problem of the achievable regret rates with online logistic regression. We derive lower bounds with logarithmic regret under $L_1$, $L_2$, and $L_\infty$ constraints on the parameter values. The bounds are…

regression