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

Content Provider	Springer Nature Link
Author	Blatz, John Fishkind, Donniell E. Priebe, Carey E.
Copyright Year	2010
Abstract	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.
Starting Page	63
Ending Page	74
Page Count	12
File Format	PDF
ISSN	14322994
Journal	Mathematical Methods of Operations Research
Volume Number	72
Issue Number	1
e-ISSN	14325217
Language	English
Publisher	Springer-Verlag
Publisher Date	2010-05-07
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Submodular function Matroid constraint Canadian travellers problem Calculus of Variations and Optimal Control; Optimization Business/Management Science Operations Research/Decision Theory
Content Type	Text
Resource Type	Article
Subject	Management Science and Operations Research Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Inverse Matroid Intersection Problem

Correction on “Optimal portfolio selection when stock prices follow an jump-diffusion process”

Portfolio optimization in stochastic markets

Efficient solution of interval optimization problem

A matroid view of key theorems for edge-swapping algorithms

Optimal portfolio selection when stock prices follow an jump-diffusion process

Generalized Pinwheel Problem

Stochastic control problems with delay

Work effort, consumption, and portfolio selection: when the occupational choice matters

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

Similar Documents

Inverse Matroid Intersection Problem

Correction on “Optimal portfolio selection when stock prices follow an jump-diffusion process”

Portfolio optimization in stochastic markets

Efficient solution of interval optimization problem

A matroid view of key theorems for edge-swapping algorithms

Optimal portfolio selection when stock prices follow an jump-diffusion process

Generalized Pinwheel Problem

Stochastic control problems with delay

Work effort, consumption, and portfolio selection: when the occupational choice matters

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