Approximation Algorithms for Solving Cost Observable Markov Decision Processes

Designing approximation algorithms to solve problems that have partial observability is the focus of this research. The model we propose (Cost Observable Markov Decision Processes or COMDPs) associates costs with obtaining information about the current state. The COMDP’s actions are of two kinds: world actions and observation actions.