AI Glossary / Reinforcement learning and robotics / Advanced
Proper policy
Definition
A proper policy is a policy that reaches the designated terminal state with probability one from the required starting states in a stochastic shortest-path problem. In the standard finite-state stationary setting, this also gives a finite expected termination time. The term is a mathematical condition about eventual termination, not a judgment that the policy is optimal, ethical, fast, or otherwise suitable for deployment.
What it means
Some decision processes are intended to finish: a robot reaches a destination, a job completes, or a procedure enters an absorbing terminal state. A policy is problematic for that model if it can keep the system outside termination forever with positive probability.
Properness distinguishes policies that eventually finish from those that may not. It must be assessed over the relevant initial states, not just one successful demonstration. The terminal state must also represent the outcome the model actually means to count as termination; silently treating a timeout as task success changes the question.
How it works
Fix the policy and examine the resulting state-transition process. For a stationary policy on a finite state space, properness requires that no nonterminal closed recurrent class can trap the process. Equivalently, the terminal state must be reached almost surely from every starting state required by the definition.
Expected termination times can be calculated from equations that count one step now plus the expected remaining steps in nonterminal successor states. In a finite proper stationary system, these expected times are finite. They can nevertheless be extremely large.
The terminology requires care beyond that setting. Infinite-state or more general formulations may define properness explicitly through finite expected termination time, sometimes together with a finite-cost condition. Almost-sure termination alone need not imply a finite expectation there, so the assumptions and definition should be stated.
Properness is useful in undiscounted dynamic programming because ongoing costs and failure to terminate can complicate value equations. But finite total cost alone is not a universal test for properness: a zero-cost loop can continue indefinitely while accumulating no additional cost.
Three practical examples
- Robot navigation models: check that a proposed policy eventually reaches the designated destination from all required initial locations.
- Job-completion models: identify policies that can become trapped in a nonterminating sequence of decisions.
- Planning algorithms: verify assumptions needed when evaluating undiscounted stochastic shortest-path policies.
Think of it this way
Think of a maze strategy that eventually leads to an exit. Properness asks whether the strategy escapes with probability one, not whether the exit is reached quickly or by the shortest route. Seeing it escape several times is encouraging evidence, but does not by itself rule out a region where it could become trapped.
Worked example
Consider a fictional finite model with one nonterminal state S and an absorbing terminal state T. An Attempt action reaches T with probability 0.25 and returns to S with probability 0.75. A Wait action always returns to S. Outcomes of successive Attempts follow the same transition probabilities.
Under the stationary policy Always Attempt, the chance of still being at S after n steps is 0.75^n. This tends to zero as n increases, so termination occurs with probability one. If E is the expected number of steps to termination, E = 1 + 0.75E, giving E = 4. The policy is proper.
However, its probability of not finishing within ten steps is 0.75^10, approximately 0.05631. Thus it has about a 5.63% chance of exceeding ten steps. A mean completion time of four is not a four-step guarantee, and properness is not a guarantee of meeting a particular deadline.
Under Always Wait, the probability of termination is zero and expected termination time is infinite. That policy is improper. If waiting has cost zero, its accumulated cost is still zero, demonstrating why finite cost alone does not establish properness.
Now consider a stationary mixed policy choosing Attempt with probability 0.50 and Wait with probability 0.50 at every visit. Its one-step termination probability is 0.50 × 0.25 = 0.125. The expected number of steps is 1/0.125 = 8, and its nontermination probability after n steps is 0.875^n. It is also proper, although slower in expectation than Always Attempt.
These conclusions concern the stated model. A real system with unmodeled failure states would require a different analysis.
Illustrative case study
Fictional case: BirchTasks evaluates a planner whose simulated episodes usually finish. A state-graph review reveals that one rarely visited configuration leads to a cycle from which the terminal state cannot be reached under the policy. The team records that the policy is improper for a requirement covering that configuration, even though most test runs succeeded.
After modifying the policy, it reassesses both eventual termination and deadline performance. This fictional case illustrates two separate checks: reaching the terminal state almost surely and reaching it quickly enough for the task. It does not report a real reliability improvement.
Common misconceptions and mistakes
Proper does not mean optimal or shortest. A policy may be proper from one state but not satisfy a definition requiring properness from all states. A finite test suite cannot generally prove almost-sure termination. Conversely, occasional long episodes do not by themselves show impropriety. The distinction between probability-one termination and bounded completion time is especially important.
Business use
This concept can clarify completion requirements in planning and workflow models. Specify which states are included, what terminal means, and whether the mathematical analysis assumes a finite stationary model. Assess expected time and deadline probabilities separately from properness. Where the transition model is estimated, report the uncertainty and evidence supporting the conclusion rather than presenting a model property as an unconditional operational guarantee.
People also ask
Can a proper policy revisit states?
Yes. The example revisits S but still terminates almost surely.
Can an improper policy have finite cost?
Yes, for example when it loops forever at zero cost.
Does probability-one termination imply a fixed maximum number of steps?
No. There can be a nonzero chance of exceeding any finite step count.
Check your understanding
Why is Always Attempt proper?
Answer: Its probability of remaining nonterminal tends to zero.
What is its expected termination time?
Answer: Four steps.
Why does the mixed policy take eight steps on average?
Answer: Its per-step termination probability is reduced to one-eighth.
Related terms
- Terminal states
- Policy evaluation
- Stochastic shortest path
- terminal state
- absorbing state
- hitting time
- stationary policy
- recurrent class
- almost-sure termination
- expected cost
Learn next
Next, identify closed nonterminal classes in a small transition graph. Then compare expected completion time with deadline probabilities and examine why infinite-state models need additional care.
More in Reinforcement learning and robotics
- PPO-Clip - PPO-Clip is the clipped-objective version of proximal policy optimization.
- PPO-Penalty - PPO-Penalty is a proximal policy optimization variant that subtracts a penalty for KL divergence between the old and candidate policies from a...
- Prioritized experience replay - Prioritized experience replay is a reinforcement-learning technique that samples some stored experiences more often than others according to an estimate of...
- Proximal policy optimization - Proximal policy optimization, or PPO, is a family of policy-gradient methods designed to improve a decision policy while discouraging excessively large...
- Q-learning - Q-learning is a model-free reinforcement learning method that updates estimates of the long-term value of taking actions in states.
- R-learning - R-learning is an off-policy reinforcement-learning control method for continuing tasks with an average-reward objective.
Sources
Prashanth L. A., Lectures on Reinforcement Learning Theory, Stochastic Shortest Path Problems: https://cse.iitm.ac.in/~prashla/notes/rlbook/sspsection.html Dimitri P. Bertsekas, Proper Policies in Infinite-State Stochastic Shortest Path Problems: https://web.mit.edu/dimitrib/www/Stable_SSP_Proper_Policies.pdf
Previous: Proper noun Next: Proportion