2018 Sriram Yenamandra’s internship

Graph planning with finite horizon consists in finding an optimal path of fixed length (the horizon, or stopping time) in a graph. Expected finite horizon is a  relaxation of this problem where the stopping time is not fixed, but can be chosen randomly, provided the expected stopping time is a fixed constant. Sriram studied the case where the variance of the stopping time distributions is fixed, to avoid unrealistic  stopping-time distributions that would assign significant probability mass towards infinity.

Sriram proved that distributions with at most three points in their support are sufficient for optimality, and that memory may be necessary in the optimal plan. He proposed and implemented an approximation algorithm to compute arbitrarily precise approximation of the optimal value.  After the internship, he continued working with his supervisor to generalize the results to distributions where the  value of higher-order moments are fixed.