An Observation of Dynamic Programming with Set-valued Translate Maps by Using Some Duality Formulations

A dynamic programming problem that each state at some stage is chosen from a set decided by the state and action at the last stage, in other words, translate maps are set-valued maps, is considered and investigated. To solve the problem, two roles of choice of next stage are introduced; one is to the player's advantage, and the other is disadvangate. Also, two duality formulations based on Fenchel-Rockafellar duality [7] and Kanniappan duality [6] for such dynamic programming problem are defined and observed.