Using Randomization to Break the Curse of Dimensionality

By John Rust. 1997

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

Reinforcement learning in robotics: A survey (2013, background): “, 1999) and can even break the curse of dimensionality (Rust, 1997).”
The stochastic lake game: A numerical solution (2006, methodology): “One is to convert the problem to a Discrete Decision Problem and to use the randomization method of Rust (1997).”
Swapping the Nested Fixed Point Algorithm: A Class of Estimators for Discrete Markov Decision Models (2002, methodology): “Rust (1997a, 1997b) shows that randomization and low discrepancy methods in the discretization of the state space can break the curse of dimensionality in the solution of these models.”
Efficient approximate planning in continuous space Markovian Decision Problems (2001, unknown): “1 The idea of the considered algorithms originates in the algorithm considered by Rust [13].”
Regression methods for pricing complex American-style options (2001, methodology): “These methods can be thought of as variants of Rust’s algorithm [17], specialized to the context of optimal stopping.”
Convergent Fitted Value Iteration with Linear Function Approximation (2011, methodology): “Further interest in batch RL methods then led to work that uses non-parametric function approximators with FVI to avoid divergence [5, 15, 16, 17].”
Is There a Curse of Dimensionality for Contraction Fixed Points in the Worst Case (2002, methodology): “If we want to use the space Bd, one possible solution is to follow Rust (1997) and switch to the randomized setting in which the bound (48) is understood as the expected error with respect to randomized sample points.”
Q-learning with Nearest Neighbors (2018, methodology): “Our Lipschitz assumptions are identical to (or less restricted than) those used in the work of [36], [11], and [17].”
A practitioner’s guide to Bayesian estimation of discrete choice dynamic programming models (2012, unknown): “To overcome the hurdle due to the curse of dimensionality problem, several studies have proposed different ways to approximate the dynamic programming solutions (e.g., Keane and Wolpin 1994; Rust 1997; Hotz and Miller 1993; Aguirregabiria and Mira 2002; Ackerberg 2009).”
Using dynamic programming with adaptive grid scheme for optimal control problems in economics (2004, methodology): “In principle also Monte–Carlo techniques like in Keane and Wolpin (1994) allow for breaking the curse of dimensionality, but as Rust (1997) points out, the specific algorithm in Keane and Wolpin (1994) uses an interpolation technique which again is subject to exponential growth of the numerical…”
Tree-Based Batch Mode Reinforcement Learning (2005, background): “The work of Ormoneit and Sen is related to earlier work aimed to solve large-scale dynamic programming problems (see for example Bellman et al., 1973; Gordon, 1995b; Tsitsiklis and Van Roy, 1996; Rust, 1997).”
Bayes Meets Bellman: The Gaussian Process Approach to Temporal Difference Learning (2003, methodology): “Specifically, our method can replace discretization based methods (see, e.g. Rust, 1997 and references therein), A significant advantage of the Gaussian process approach is that an error estimate is provided at no extra cost.”
Finite-Time Bounds for Fitted Value Iteration (2008, methodology): “This latter class of MDPs has been considered in many previous theoretical works (e.g., Chow and Tsitsiklis, 1989, 1991; Rust, 1996b; Szepesvári, 2001).”