LOWER BOUNDING AGGREGATION AND DIRECT COMPUTATION FOR AN INFINITE-HORIZON ONE-RESERVOIR MODEL

We present a specialized policy iteration method for the computation o f optimal and approximately optimal policies for a discrete-time model of a single reservoir whose discharges generate hydroelectric power. The model is described in (Lamond ct al., 1995) and (Drouin ct al., 19 96), where the special structure of optimal policies is given and an a pproximate value iteration method is presented, using piecewise affine approximations of the optimal return functions. Here, we present a fi nite method for computing an optimal policy in O(n(3)) arithmetic oper ations, where n is the number of states in the associated Markov decis ion process, and a finite method for computing a lower bound on the op timal value function in O(m(2)n) where m is the number of nodes of the piecewise affine approximation.