State-Space Planning and Random-Sample Q-Planning

Planning Through States

State-space planning treats each possible situation as a location in a search space. An agent considers how actions move it from one state to another, then uses value information to guide a policy or path toward a goal. The central planning question is therefore two-part: where will an action take the agent, and how valuable is the resulting state?

Random-sample Q-planning is a particular short planning process. It first selects a state S and an action A at random. It sends that pair to a sample model, which supplies a sampled reward R and a sampled next state S′. It then applies one-step tabular Q-learning to update the selected Q(S, A) entry. One planning step therefore turns one randomly selected state-action pair into one Q-value update.

Tracing One Planning Step

Consider a generated state set containing Entrance, Hallway, and Goal. These names are only an illustrative practice setting. Suppose a planning step randomly selects Hallway as S and an available action as A. At this moment, the selected pair identifies the Q(Hallway, A) entry that the step will address. The selection itself does not yet provide a reward or a next state.

The selected S and A are inputs to the sample model. The model returns the missing transition information: a sampled reward R and a sampled next state S′. This separation is important. The random selection identifies which Q-value entry is being addressed, while the model supplies the outcome information used by the update.

Updating the Selected Entry

Before the update, the selected Q(S, A) entry has its current value. After the sample model returns R and S′, the one-step tabular Q-learning rule combines the current state, selected action, sampled reward, and sampled next state to produce a new value for that same selected entry. The operation changes Q(S, A); it does not turn the randomly selected pair into a different pair.

State-Space Structure

State-space planning searches through states rather than through complete plans. Actions move the process from state to state, and value functions evaluate states. Those value functions act as an intermediate guide toward improving the policy: simulated experience is processed through backup operations, the resulting value information is used to improve the policy, and the policy guides choices among actions.

The shared structure is more important than the names of the generated states. A planning method uses simulated experience, applies backup operations to compute or update value functions, and uses those values as an intermediate step toward improving the policy. This is the common architecture of state-space planning methods described here.

Two Planning Spaces

Do not treat these labels as interchangeable. State-space planning searches states for an optimal policy or path to a goal. Plan-space planning searches a space of plans; its operators transform one plan into another, and its value functions are defined over plans rather than states. Partial-order planning is a plan-space example in which the ordering of steps can remain partly undetermined during some stages.

Common Misunderstandings

• Treating the random state-action selection as if it already contained the reward and next state.

  The selected S and A identify the Q-value entry, but the sample model supplies R and S′.

  Fix: Trace the process in order: select S and A, send them to the sample model, receive R and S′, then update Q(S, A).

• Confusing the current Q-value with the updated Q-value.

  The current Q(S, A) is the value before the one-step operation; the updated Q(S, A) is the value after the operation.

  Fix: Use the words current and updated to mark the two different points in the trace.

• Assuming that the update changes every Q-value entry.

  The described step addresses the selected Q(S, A) entry.

  Fix: Follow the randomly selected state and action and identify that single entry as the target of the step.

• Treating simulated experience as unrelated to value functions.

  Simulated experience is processed through backup operations to compute value functions, which then help improve the policy.

  Fix: Place the backup between simulated experience and policy improvement in your mental model.

• Calling state-space planning plan-space planning.

  State-space planning searches states and uses actions to move between them. Transforming plans belongs to plan-space planning.

  Fix: Ask what object is being searched: states in state-space planning, plans in plan-space planning.

Practice Trace

Key Takeaways

1. Random-sample Q-planning begins by randomly selecting a state S and an available action A.
2. The selected pair identifies the Q(S, A) entry addressed by the planning step.
3. A sample model receives S and A and returns a sampled reward R and next state S′.
4. One-step tabular Q-learning uses the current Q-value and sampled transition information to produce an updated value for the selected entry.
5. State-space planning searches states, uses actions to move between states, and uses value functions to help improve a policy; plan-space planning searches and transforms plans.