Reinforcement Learning and Stochastic Optimization

Part III – State-dependent Problems

We now transition to a much richer class of dynamic problems where some aspect of the problem depends on dynamic information. This might arise in three ways:

• The objective function depends on dynamic information, such as a cost or price.
• The constraints may depend on the availability of resources (that are being controlled dynamically), or other information in constraints such as the travel time in a graph or the rate at which water is evaporating.
• The distribution of a random variable such as weather, or the distribution of demand, may be varying over time, which means the parameters of the distribution are in the state variable.

When we worked on state-independent problems, we often wrote the function being maximized as $F(x,W)$ to express the dependence on the decision $x$ or random information $W$, but not on any information in our state $S_t$ (or $S^n$). As we move to our state-dependent world, we are going to write our cost or contribution function as $C(S_t,x_t)$ or, in some cases, $C(S_t,x_t,W_{t+1})$, to capture the possible dependence of the objective function on dynamic information in $S_t$. In addition, our decision $x_t$ might be constrained by $x_t\in {\mathcal{X}}_t$, where the constraints ${\mathcal{X}}_t$ may depend on dynamic data such as inventories, travel times, or conversion rates.

Finally, our random information $W$ may itself depend on known information in the state variable $S_t$, or possibly on hidden information that we cannot observe, but have beliefs about (these beliefs would also ...