Reinforcement Learning and Stochastic Optimization

4 Introduction to Stochastic Search

Our most basic optimization problem can be written

    (4.1)

where x is our decision and W is any form of random variable. A simple example of this problem is the newsvendor problem which we might write

where x is a quantity of product we order at cost c, W is the demand, and we sell the smaller of x and W to the market at a price p.

This problem is the one most identified with the field that goes under the name of “stochastic search.” It is typically presented as a “static” stochastic optimization problem because it consists of making a single decision x, then observing an outcome W allowing us to assess the performance F(x, W), at which point we stop. However, this all depends on how we interpret “F(x, W),” “x,” and “W.”

For example, we can use F(x, W) to represent the results of running a simulation, a set of laboratory experiments, or the profits from managing a fleet of trucks. The input x could be the set of controllable inputs that govern the behavior of the simulator, the materials used in the laboratory experiments, or the size of our fleet of trucks. In addition, x could also be the parameters of a policy for making decisions, such as the order-up-to parameters θ = (θ^min, θ^max) in the inventory problem we introduced in section 1.3 ...