Efficient Exploration and Value Function Generalization in Deterministic Systems

By Zheng Wen, Benjamin Van Roy. 2013

76 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Deep Exploration via Bootstrapped DQN (2016, background): “Except for particular deterministic contexts [27], OFU methods that lead to e cient RL in complex domains have been computationally intractable.”
Generalization and Exploration via Randomized Value Functions (2014, methodology): “As such, our algorithm and results also serve as contributions to approximate dynamic programming.”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, neutral): “Similar goals have been attempted by Wen and Van Roy [2013] and Krishnamurthy et al. [2016] where attention is restricted to decision processes with deterministic dynamics and special structures.”
Deep Exploration via Randomized Value Functions (2017, background): “These contributions represent important developments, but OCP is not suitable for stochastic systems and is highly sensitive to model misspecification, and generalizing effectively in high-dimensional state spaces calls for methods that extrapolate.”
On Oracle-Efficient PAC RL with Rich Observations (2018, methodology): “We construct a family of MDPs as shown in Figure 2 that encodes the 3-SAT problem for this formula as follows: For each variable x i there are two terminal states x 1 i and x 0 i corresponding to the Boolean assignment to the variable.”
Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle (2019, methodology): “The seminal work by Wen and Van Roy [36] proposed an algorithm, optimistic constraint propagation (OCP), which enjoys polynomial sample complexity bounds for a family of Q -function classes, including the linear function class as a special case.”
Provably Efficient Reinforcement Learning with Linear Function Approximation (2019, background): “Finally, in a broader context, without the assumption of a linear MDP, sample efﬁciency guarantees have been established for RL under other assumptions, such as that the transition dynamics are fully deterministic [46, 47], or have low variances [18].”
On Reward-Free Reinforcement Learning with Linear Function Approximation (2020, methodology): “For deterministic systems, under the assumption that the optimal Q -function is linear, there exists a polynomial sample complexity upper bound [Wen and Van Roy, 2013] in the standard RL setting.”
Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches (2018, background): “On the model-based side, Lattimore et al. (2013) and Osband and Van Roy (2014a) obtain sample complexity guarantees; the former makes no assumptions but the guarantee scales linearly with the model class size, and the latter makes continuity assumptions, so both results have more limited scope than ”
Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning? (2019, methodology): “Since Wen & Van Roy (2013) showed polynomial sample complexity upper bound when the representation can perfectly predict the Q -function, our lower bound on policy-based learning, which applies to perfect representations, thus demonstrates that the ability of predicting the Q -function is much…”