Approximate Policy Iteration Schemes: A Comparison

By Bruno Scherrer. 2014

101 citations recorded by the source corpus.

We consider the infinite-horizon discounted optimal control problem formalized by Markov Decision Processes. We focus on several approximate variations of the Policy Iteration algorithm: Approximate Policy Iteration (API) (Bertsekas & Tsitsiklis, 1996), Conservative Policy Iteration (CPI) (Kakade & Langford, 2002), a natural adaptation of the Policy Search by Dynamic Programming algorithm (Bagnell et al., 2003) to the infinite-horizon case (PSDP∞), and the recently proposed Non-Stationary Policy Iteration (NSPI(m)) (Scherrer & Lesner, 2012). For all algorithms, we describe performance bounds with respect the per-iteration error e, and make a comparison by paying a particular attention to the concentrability constants involved, the number of iterations and the memory required. Our analysis highlights the following points: 1) The performance guarantee of CPI can be arbitrarily better than that of API, but this comes at the cost of a relative--exponential in 1/e increase of the number of iterations. 2) PSDP1 enjoys the best of both worlds: its performance guarantee is similar to that of CPI, but within a number of iterations similar to that of API. 3) Contrary to API that requires a constant memory, the memory needed by CPI and PSDP∞ is proportional to their number of iterations, which may be problematic when the discount factor γ is close to 1 or the approximation error e is close to 0; we show that the NSPI(m) algorithm allows to make an overall trade-off between memory and performance. Simulations with these schemes confirm our analysis.

Subfields: Artificial Intelligence, Computer Networks and Communications, Reinforcement Learning

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 Computer Networks and Communications

In Reinforcement Learning

Citations in the corpus

Conservative Q-Learning for Offline Reinforcement Learning (2020, background): “Prior analyses have also focused on error propagation in approximate dynamic programming [13, 8, 63, 56, 32], and generally obtain bounds in terms of concentrability coefficients that capture the effect of distribution shift.”
DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correction (2020, methodology): “(Munos, 2005; Munos and Szepesvári, 2008; Farahmand et al., 2010; Scherrer et al., 2015; Lesner and Scherrer, 2013; Scherrer, 2014) focused on analysing error induced in Bellman projections, under the assumption of an abstract error model.”
Dual Policy Iteration (2018, methodology): “5 and classic API policy improvement procedure is that we use η n ’s disadvantage function A η n , i.e., we are performing imitation learning by treating η n as an expert in this iteration [24, 33].”
Reinforcement and Imitation Learning via Interactive No-Regret Learning (2014, methodology): “Previous methods like [4, 15, 28] provide a much stronger, multiplicative error guarrantee when we consider competing against the bayes optimal policy in a fully observed MDP.”
Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison (2020, methodology): “Doing so can be tricky given the complicated expression, and we provide 3 verification methods following the conventions in the literature [Scherrer, 2014]: The first one is to observe that FQI has quadratic dependence on horizon and our bound for MSBO has a 1/(1−γ) net improvement over FQI [Chen an”
Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning? (2019, methodology): “…ﬁrst class of methods include those based on witness rank, Belman rank, and the Eluder dimension, while the latter two classes of algorithms make assumptions either on concentrability coefﬁcients or on distribution mismatch coefﬁcients (see Agarwal et al. (2019); Scherrer (2014) for discussions).”
Action Robust Reinforcement Learning and Applications in Continuous Control (2019, unknown): “Soft PR-PI can be seen as a generalization of Conservative PI (CPI) to solving PR-MDPs.”
Provably Good Batch Reinforcement Learning Without Great Exploration (2020, methodology): “When comparing to onpolicy policy optimization [15, 34, 2, 13], the constant C is akin to the density ratio with respect to an optimal policy in those works, though we pay an additional price on the size of densities.”
Bellman-consistent Pessimism for Offline Reinforcement Learning (2021, background): “Notably, these milder coverage assumptions in Corollaries 1 and 2 provide offline RL counterparts to the benefits of policy-gradient-style methods with online access to the environment [Kakade and Langford, 2002; Scherrer, 2014; Agarwal et al., 2019].”
Mastering the game of Go without human knowledge (2017, background): “…superhuman performance, winning 100–0 against the previously published, champion-defeating AlphaGo. repeatedly in a policy iteration procedure 22,23 : the neural network’s parameters are updated to make the move probabilities and value ( p , v ) = f θ ( s ) more closely match the improved…”
Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes (2019, methodology): “…et al. [2010]) and those which work with a restricted policy class, making incremental updates, such as Conservative Policy Iteration (CPI) [Kakade and Langford, 2002] and Policy Search by Dynamic Programming (PSDP) [Bagnell et al., 2004] (also see [Scherrer and Geist, 2014, Scherrer, 2014]).”
Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism (2021, background): “C imposes a much weaker assumption in contrast to other concentrability requirements which involve taking a maximum over all policies; see [42] for a hierarchy of different concentrability definitions.”
Reinforcement Learning: Theory and Algorithms (2019, background): “See [Scherrer, 2014] for more a detailed discussion and comparison of some of these approaches.”
Is the Bellman residual a bad proxy? (2016, background): “It is even better due to the involved concentrability coefficient (the ones for value-based bounds are worst, see [21] for a comparison).”
On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift (2019, methodology): “In terms of the concentrability coefficient C∞ and the “distribution mismatch coefficient” D∞ in Table 2 , we have that D∞ ≤ C∞, as discussed in [Scherrer, 2014] (also see the table caption).”