Solving MDPs with Skew Symmetric Bilinear Utility Functions
Gilbert, Hugo (Sorbonne Universités, UPMC University of Paris 06, UMR 7606, LIP6 and CNRS, UMR 7606, LIP6) | Spanjaard, Olivier (Sorbonne Universités, UPMC University of Paris 06, UMR 7606, LIP6 and CNRS, UMR 7606, LIP6) | Viappiani, Paolo (Sorbonne Universités, UPMC University of Paris 06, UMR 7606, LIP6 and CNRS, UMR 7606, LIP6) | Weng, Paul (SYSU-CMU Joint Institute of Engineering, Guangzhou and SYSU-CMU Shunde International Joint Research Institute, Shunde)
In this paper we adopt Skew Symmetric Bilinear (SSB) utility functions to compare policies in Markov Decision Processes (MDPs). By considering pairs of alternatives, SSB utility theory generalizes von Neumann and Morgenstern's expected utility (EU) theory to encompass rational decision behaviors that EU cannot accommodate. We provide a game-theoretic analysis of the problem of identifying an SSB-optimal policy in finite horizon MDPs and propose an algorithm based on a double oracle approach for computing an optimal (possibly randomized) policy. Finally, we present and discuss experimental results where SSB-optimal policies are computed for a popular TV contest according to several instantiations of SSB utility functions.
Jul-15-2015