Open Access. Powered by Scholars. Published by Universities.®
Operations Research, Systems Engineering and Industrial Engineering Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Operations Research, Systems Engineering and Industrial Engineering
Sampled Fictitious Play For Multi-Action Stochastic Dynamic Programs, Archis Ghate, Shih-Fen Cheng, Stephen Baumert, Daniel Reaume, Dushyant Sharma, Robert L. Smith
Sampled Fictitious Play For Multi-Action Stochastic Dynamic Programs, Archis Ghate, Shih-Fen Cheng, Stephen Baumert, Daniel Reaume, Dushyant Sharma, Robert L. Smith
Research Collection School Of Computing and Information Systems
We introduce a class of finite-horizon dynamic optimization problems that we call multi-action stochastic dynamic programs (DPs). Their distinguishing feature is that the decision in each state is a multi-dimensional vector. These problems can in principle be solved using Bellman's backward recursion. However, complexity of this procedure grows exponentially in the dimension of the decision vectors. This is called the curse of action-space dimensionality. To overcome this computational challenge, we propose an approximation algorithm rooted in the game theoretic paradigm of Sampled Fictitious Play (SFP). SFP solves a sequence of DPs with a one-dimensional action-space, which are exponentially smaller than …