Reinforcement Learning and Stochastic Optimization

Part IV – Policy Search

Policy search is a strategy where we define a class of functions that determine a decision, and then search for the best function within that class. Policies in the policy search class can be divided into two subclasses:

• Policy function approximations (PFAs) – PFAs are analytical functions that relate information in the state variables to decisions. PFAs come in three (overlapping) forms: lookup tables, parametric models, and nonparametric (or locally parametric) models, which are the same classes of functions used in machine learning. PFAs are typically limited to scalar actions or low-dimensional controls.

  PFAs are covered in chapter 12, along with a general discussion of methods for policy search.

• Cost function approximations (CFAs) – Parametric CFAs are parameterized optimization problems, where the parameterization guides the optimization problem to produce decisions that work well (a) over time and (b) under uncertainty. We first saw a parametric CFA in chapter 7 in the form of policies for multiarmed bandit problems such as an interval estimation policy

  

  where $\mathcal{X}=\{x_1,\dots ,x_M\}$ is a discrete set of alternatives (ads, drugs) and where ${\overline{\mu }}_x^n$ is our current estimate of the performance of alternative $x$ after $n$ experiments, and ${\overline{\sigma }}_x^n$ is the standard deviation of ${\overline{\mu }}_x^n$. The parameter $\theta$ has to be tuned to optimize the policy.

  The presence of the “$\text{arg}\text{max}$” operator opens ...