Prof. Justin Goodson, Saint Louis University (USA)
Chair: Prof. Luca Bertazzi, Università di Brescia
When: May 27th, 2026, 11:00 AM
Where: Sala della Biblioteca, via San Faustino 74/b
Max-min dynamic programs model sequential decision problems where policies are evaluated via the worst-case reward across a set of scenarios representing future uncertainty. In the standard backward induction algorithm for max-min dynamic programs, the effort required to identify an optimal policy grows exponentially with the number of state variables. We develop a bounded backward induction (BBI) procedure that uses upper and lower bounds on rewards-to-go to curb this exponential growth by eliminating suboptimal decisions. BBI shifts the problem of dimensionality to the task of identifying strong and tractable bounds. We propose a dual bounding technique that reduces the uncertainty faced by the decision maker. The technique leads to families of dual bounds that vary in strength and in the computational effort required to obtain them. Policies are recovered by embedding dual bounds in a lookahead procedure, which in turn yields a policy performance guarantee. For budget-style scenario sets, we provide results that ease the optimization required for policy evaluation and dual bound calculation. We demonstrate the utility of BBI via application to a media selection problem with yield uncertainty. BBI identifies optimal policies for problem instances orders of magnitude larger than what is tractable with conventional backward induction.