Does a partial program have to be written in ALisp?

No. ALisp is a research language illustrating the approach; other formalisms can express constrained programs with unresolved choices.

Can the same choice point select different alternatives on different visits?

Yes. A completion policy can condition on relevant state and execution context.

Is filling a program hole always reinforcement learning?

No. Program synthesis may fill holes using logical specifications or examples. The completion method depends on the formal setting.

AI Glossary / Graphs and symbolic AI / Advanced

Partial program

Definition

A partial program is a program specification that deliberately leaves some choices unresolved. In programmable reinforcement learning, it supplies control structure and permitted actions while a learning method determines how to choose at the remaining choice points.

What it means

The program can require selecting an item, moving to it and delivering it, while leaving item or route choices to a learned policy.

The partial program defines allowed behaviors, and learning searches within those restrictions rather than prescribing every decision in advance.

The term also appears in program synthesis, where holes are filled to satisfy a specification. This entry focuses on the hierarchical reinforcement-learning sense associated with languages such as ALisp. It does not mean that an accidentally unfinished script is ready to run without a defined mechanism for resolving its missing choices.

How it works

A designer writes the fixed control structure, including sequences, loops or subroutine calls, and marks permitted alternatives at choice points. Primitive actions affect the environment; ordinary computation manages program flow.

When execution reaches a choice point, a completion policy selects an allowed alternative. The useful decision state can include both the environment state and the program's execution context, such as its current instruction, call stack or memory.

Learning evaluates choices through rewards and their future consequences. A choice that looks cheap immediately may make the remaining task expensive. Hierarchical methods use the supplied structure to organize this problem, but the structure also restricts the policies the learner can represent.

An optimal completion, when established under a method's assumptions, is optimal among policies consistent with that partial program. It need not match the unrestricted environment's globally best policy. Incorrect structural restrictions can therefore prevent success or exclude better behavior.

Three practical examples

A simulated courier receives a fixed collect-then-deliver routine while learning which eligible parcel to serve next.
A game agent uses programmed task hierarchy but learns resource and movement choices at designated points.
A research system compares alternative state abstractions for the choice policy while keeping the same partial program and environment.

Think of it this way

Think of a recipe that fixes essential preparation steps but asks a cook to choose among permitted ingredients based on what is available. The recipe narrows the choices while leaving decisions to be resolved in context.

The analogy is limited because reinforcement learning optimizes a defined reward process rather than relying on a cook's judgment. The choice rules must also account for relevant execution context, and a poorly designed recipe can exclude the best meal regardless of how cleverly its remaining choices are made.

Worked example

Consider an invented deterministic task with a required sequence: choose a depot, collect a package there, then deliver it to the destination. The partial program allows only depot A or depot B.

Travel to A costs 2 units and delivery from A costs 9, giving total cost 11. Travel to B costs 5 and delivery from B costs 3, giving total cost 8. With reward equal to negative total cost, a completion selecting B receives −8 rather than −11 and is better within these choices.

Suppose the environment also contains depot C with total cost 4, but the partial program does not permit choosing it. Even a perfectly learned completion of the supplied program cannot select C. Its best achievable result remains cost 8.

This assumes fixed costs and no other decisions. It illustrates constrained completion and future consequences; it is not evidence that a particular learning algorithm has converged.

Illustrative case study

The fictional Alder Agents team supplies a partial program for a delivery simulator. Its first hierarchy insists on returning to a central station between deliveries, although the environment sometimes permits direct travel between destinations.

The learning system improves its choices within that routine but cannot remove the programmed return step. Alder identifies the restriction, revises the program and evaluates the new allowed behavior separately.

The fictional lesson is that disappointing performance can come from the supplied program as well as the learner. Reviewing the space of permitted policies is as important as tuning the learning process.

Common misconceptions and mistakes

A partial program is merely broken code. In this setting, unresolved choices are intentional and have defined semantics.
Learning can override any programmed restriction. A consistent completion must respect the supplied structure.
The same physical state always requires the same choice. Program context can distinguish situations with different remaining tasks.
Optimal completion means unrestricted optimal behavior. The guarantee is relative to the allowed policies and the method's assumptions.
Choice points remove the need for an objective. Rewards or specifications still determine what counts as a good completion.

Business use

Partial programming is useful when domain specialists know a task's broad structure but cannot conveniently specify every context-dependent decision. It can make the intended behavior easier to inspect and reduce parts of the search space.

For a practical evaluation, document which actions and sequences are fixed, which choices are learnable, and which state information the choice policy receives. Compare outcomes against alternatives that test whether the hierarchy itself is unnecessarily restrictive.

Do not treat a structured program as an automatic behavioral guarantee. Its control logic, action implementation, reward design and learned choices all require evaluation. A theoretical convergence result applies only under its stated assumptions, which may differ from approximate training in a large simulator.

Check your understanding

Why can the learned program fail to select depot C even though its cost is lowest?

Answer: The partial program permits only A and B. Learning an optimal completion within that restricted space cannot introduce an excluded alternative; the program itself must be revised to allow C.

Related terms

Hierarchical reinforcement learning
State abstraction
Reward
ALisp
choice point
completion policy
program synthesis
semi-Markov decision process

Learn next

Write a short task outline with two explicit choice points. Separate fixed control flow from permitted alternatives, then identify the state needed at each choice. Check whether the outline accidentally excludes a feasible strategy that could achieve a better total outcome.

Sources

Andre and Russell describe partial programs and state abstraction for programmable reinforcement-learning agents: https://people.eecs.berkeley.edu/~russell/papers/aaai02-alisp.pdf

Marthi and colleagues explain ALisp choice points and concurrent hierarchical reinforcement learning: https://people.eecs.berkeley.edu/~russell/papers/ijcai05-chrl.pdf

The depot calculation and Alder Agents case are original illustrations of deliberate partial programming in AI.

Previous: Partial-order planning Next: Partial regression