A classical STRIPS operator is described by a precondition and a set of effects. The former identifies the set of states in which the action can be executed, and the latter describes how the input state changes as a result of taking the action. A probabilistic STRIPS operator (PSO) extends the STRIPS representation in two ways. First, it allows actions to have different effects depending on context, and second, it recognizes that the effects of actions are not always known with certainty.

Formally, a PSO consists of a set of mutually exclusive and exhaustive logical formulae, called contexts, and a stochastic effect associated with each context. Intuitively, a context discriminates situations under which an action can have differing stochastic effects. A stochastic effect is itself a set of change sets -- a simple list of variable values with a probability attached to each change set, with the requirement that these probabilities sum to one. The semantics of a stochastic effect can be described as follows; when the stochastic effect of an action is applied at state s, the possible resulting states are determined by the change sets, each one occurring with the corresponding probability; the resulting state associated with a change set is constructed by changing variable values at state s to match those in the change set, while all unmentioned variables persist in value. Note that since only one context can hold in any state s, the transition distribution for the action at any state s is easily determined.