Abstract
Partially Observable Adaptive Programming System (POAPS) is a novel framework designed to bridge the gap between high-level procedural programming and optimal decision-making under uncertainty. By abstracting the complexities of Partially Observable Markov Decision Processes (POMDPs) into reusable code primitives, POAPS allows non-experts to develop programs that behave like mathematically sound, optimized agents. This paper demonstrates how POAPS enables the creation of sophisticated, adaptive workflows—particularly in crowdsourcing—without requiring users to manually define state spaces or transition probabilities.
Introduction
Optimal decision-making under uncertainty is a cornerstone of artificial intelligence, yet it remains notoriously difficult to implement. The gold standard for such problems is the POMDP, a mathematical framework that accounts for hidden information (e.g., the true quality of a worker's output) and noisy observations. However, constructing a POMDP is a "high-bar" task, requiring the formalization of abstract hidden states, complex transition functions, and observation models. Consequently, many practitioners in fields like crowdsourcing rely on sub-optimal heuristics—simple rules of thumb—because they lack the expertise to build formal planning models.
POAPS addresses this challenge by "hiding" the POMDP inside familiar procedural logic, allowing developers to focus on the structure of their tasks while the system handles the underlying optimization.
The POAPS Language and Primitives
The system introduces a Lisp-based language with three core innovations designed to separate mathematical complexity from program logic.
1. The choose Construct
The central feature of the POAPS language is the (choose ...) construct. This keyword marks a decision point where the program must determine the optimal path (e.g., "Should I hire another worker or stop and return the current result?"). By explicitly defining these choice points, the programmer provides the structure of a policy, which the system then optimizes.
2. The Expert/Non-Expert Divide
POAPS utilizes a library of "primitives"—reusable building blocks created by experts. These primitives include both a standard function (e.g., hire-worker) and its underlying mathematical model. Non-experts simply call these primitives like standard functions. While the programmer sees a "Normal" value (such as a string of text), the system maintains a hidden "POAPS" value—a probability distribution representing the uncertainty of that data.
3. Dual-Value Variables
Every variable in POAPS acts as a dual entity: it holds a concrete value for the programmer to manipulate and a hidden probability distribution for the AI to optimize. This allows for a "separation of concerns" where the user handles the workflow logic while the system manages the probabilistic state.
Compilation and Online Planning
To execute these programs efficiently, POAPS compiles the code into a Hierarchical Abstract Machine (HAM). This representation maps the procedural logic into a state-space that the system can solve as a POMDP.
To solve the resulting POMDP in real-time, the authors developed C-RTDP (Choice-Real-Time Dynamic Programming). This online Monte Carlo planner focuses its computational effort specifically on the "choice points" defined in the code. Because the system knows exactly where decisions are required, it can ignore vast portions of the state space that do not involve active decision-making, making online planning feasible even for complex programs.
Experimental Evaluation
The system was evaluated through practical crowdsourcing applications and classic robotics benchmarks:
- Named Entity Recognition (NER): In a live experiment on Amazon Mechanical Turk involving 1,100 tasks, the POAPS-generated agent achieved an accuracy of 87.73% at an average cost of 4.33 cents per task. This performance was statistically equivalent to hand-crafted POMDPs designed by experts for the same specific problem.
- Complex Workflows: The language successfully implemented well-known crowdsourcing patterns such as "Iterative Improvement" and "Find-Fix-Verify" with minimal code.
- Generality: Beyond crowdsourcing, POAPS was used to model the "RockSample" problem, a standard robotics benchmark, proving its utility across diverse domains.
Discussion and Future Work
POAPS demonstrates that programs can serve as partial policies, where the user provides the structure and the compiler fills in the optimal behavior. However, several challenges remain. As programs grow in complexity, the resulting POMDPs face "state explosion," necessitating future research into state abstraction. Additionally, while Lisp is ideal for symbolic manipulation, moving toward more familiar syntax like Python could increase adoption. Future iterations may also incorporate reinforcement learning to allow the system to refine its primitive models based on real-world experience rather than relying solely on expert-provided definitions.
By making high-level AI planning accessible through standard programming paradigms, POAPS represents a significant step toward democratizing the use of optimal decision-making frameworks.
Summary updated