Rigorous Systems Research Group (RSRG) Seminar

We consider the problem of tracking a Markovian random process with a known transition matrix. The decision-maker must select as an action a state at each time step in order to maximize the total expected discounted reward which depends on the selected state and the actual state of the background Markovian process. The decision-maker is faced with asymmetries both in cost and observation: in case the selected state is less than the actual state of the Markovian process, there is an under-utilization cost and only partial observation about the actual state is revealed (that is the actual state is somewhere higher than the selected state); otherwise, the decision incurs an over-utilization cost and reveals full information about the actual state.

Formulating the problem as a Partially Observable Markov Decision Process provides a dynamic program (DP) to maximize the total expected discounted reward.  Unfortunately, the corresponding DP is defined on an uncountable state space, with little hope for a computationally feasible solution. We prove some structural results providing bounds on the optimal actions. Based on the bounds of the optimal actions, we introduce a new heuristic policy. We evaluate it by simulation and show that it outperforms the myopic policy and performs close to a set of sophisticated finite look-ahead policies that approximate the optimal.