Efficient, optimal stochastic-action selection when limited by an action budget

The problem that we consider here is a basic operations research problem, but it also a special case of the Stochastic Shortest Path with Recourse Problem and the Canadian Travellers Problem in the probabilistic path planning literature, and it is also a special case of maximizing a submodular set function subject to a matroid constraint. Specifically, suppose an agent has a task and suppose that there is a set of actions, any of which the agent might perform, with respective probabilities of the actions successfully accomplishing the task and respective rewards for the agent if the actions are successful; the agent is to select a sequence of some of these actions that will be performed sequentially, until the task is accomplished or the selected actions are exhausted, but there is a budget on the number of actions that can be performed. We provide an efficient algorithm that chooses a sequence of actions that, under the budget, maximize the agent’s expected reward. An example illustrates how, when conditioning on partial selection of actions, there can be changes to the order of the remaining actions’ adjusted utilities. However, we prove and exploit a nesting result involving solutions. Copyright Springer-Verlag 2010