Decision making under uncertainty: scalability and applications
Daniel S. Weld, Peng Dai · 2011
Almost every decision problem in the world involves uncertainty, thus falling in the category of decision making under uncertainty. Markov decision processes (MDPs) are a powerful and widely-adopted formulation for modeling decision making under uncertainty problems. Exact solutions to MDPs are commonly found using dynamic programming techniques. While the time complexity of dynamic programming algorithms is polynomial in the number of states, the algorithms can become very slow if the state space is large. Additionally, the entire MDP model needs to be loaded in memory before dynamic programming can be applied. This prohibitive use of memory is the major bottleneck in scaling MDP algorithms to real-world problems. To speed up optimal dynamic programming, we develop the solver, focused topological value iteration (FTVI), that combines using the graphical information of a problem with a heuristic-guided search. In most cases, FTVI's convergence speed outperforms state-of-the-art MDP solvers by an order of magnitude while keeping the same level of accuracy. We characterize the type of domains where FTVI excels. To overcome the memory bottleneck of dynamic programming, we developed the solver, partitioned external-memory value iteration (PEMVI), that utilizes external memory. PEMVI divides the state space into partition blocks and performs (one or more) backups on all states in a piecemeal fashion. Our automatic, domain-independent partitioning algorithm for PEMVI uses static problem analysis to identify candidates for partitions, and chooses a suitable partition using heuristic search. Surprisingly, the automatic partitioning engine, without using any domain-specific information, constructs more effective partitions than manually constructed partitions, which further improves scalability. While decision making under uncertainty is well studied, it can be applied to current problems. We find it especially interesting to apply it in quality control in crowdsourcing. Crowdsourcing refers to outsourcing tasks to a crowd of unknown people (workers) as an open call. It has become immensely popular with hoards of employers (requesters), who use it to solve a wide variety of jobs, such as dictation transcription and content screening. While the labor are easy to find and usually cheap, it is costly to track the quality of individual work. To do so, requesters often subdivide a large task into a chain of small-sized subtasks. Those subtasks are then often combined into a complex, iterative workflow, in which workers check and improve each others' results. We model the crowdsourced workflow control problem as a partially-observable MDP (POMDP), and propose a method to perform quality control automatically. Specifically, we design and implement an agent, TURK ONTROL, which learns a proposed mathematical model on workers' competency and uses it to dynamically control the workflow. Our model and agent are demonstrated to be useful in practice—the dynamic workflow computed by TUR KONTROL generates statistically-significant, better results than a non-adaptive workflow, while incurring the same amount of cost.