Reinforcement Learning and Stochastic Optimization

8 State-dependent Problems

In chapters 5 and 7, we introduced sequential decision problems in which the state variable consisted only of the state of the algorithm (chapter 5) or the state of our belief about an unknown function $\mathbb{E}\{F(x,W)|S_0\}$ (chapter 7). These problems cover a very important class of applications that involve maximizing or minimizing functions that can represent anything from complex analytical functions and black-box simulators to laboratory and field experiments.

The distinguishing feature of state-dependent problems is that the problem being optimized now depends on our state variable, where the “problem” might be the function $F(x,W)$, the expectation (e.g. the distribution of $W$), or the feasible region $\mathcal{X}$. The state variable may be changing purely exogenously (where decisions do not impact the state of the system), purely endogenously (the state variable only changes as a result of decisions), or both (which is more typical).

There is a genuinely vast range of problems where the performance metric (costs or contributions), the distributions of random variables $W$, and/or the constraints, depend on information that is changing over time, either exogenously or as a result of decisions (or both). When information changes over time, it is captured in the state variable $S_t$ (or $S^n$ if we are counting events with $n$).

Examples of state variables that affect the problem itself include:

• Physical state variables, which might include inventories, the location of a vehicle ...