Concepts / Episodes and Time Steps in Reinforcement Learning

Episodes and Time Steps in Reinforcement Learning

A lowercase symbol often identifies an individual item, while an uppercase symbol can describe a set of possible items. A subscript such as t identifies a particular time step.

  • Programming

A Symbol Can Describe One Thing or Many

Markov Decision Processes use a small set of symbols to describe what exists in the process and when it occurs. The main groups are states, actions, rewards, and time steps. The first question to ask about any symbol is whether it describes one item or a set of possible items. The second is whether it identifies a particular time.

Key point

A lowercase symbol often identifies an individual item, while an uppercase symbol can describe a set of possible items. A subscript such as t identifies a particular time step.

sone stateSnonterminal statesaone actionS+inclusive state setrone rewardA(s)actions available in sRpossible rewardsindividual versus setindividual versus setindividual versus set
How does the notation distinguish one state, action, or reward from a set of possible states, actions, or rewards?

The Main MDP Notation

IdeaIndividual notationSet or context notationMeaning
States or s′S and S+A state notation; S describes nonterminal states and S+ describes the inclusive state set.
ActionaA(s)An action, or the set of actions available in state s.
Action at a timeA_t—The action identified at time step t.
RewardrRAn individual reward, or the set of all possible rewards.
State at a timeS_t—The state identified at time step t.

Use the notation table by checking both the object type and any time subscript.

The symbols s and s′ refer to state notation for individual states. The symbols S and S+ describe state sets: S describes nonterminal states, while S+ describes the inclusive state set. For actions, a is an individual action and A(s) is the action set associated with state s. Rewards use r for an individual reward and R for the set of all possible rewards.

Following Time Through an Episode

A time subscript tells you which occurrence is being discussed. In S_t, t identifies the state associated with time step t. In A_t, t identifies the action associated with time step t. The subscript does not turn the symbol into a set; it adds a time reference to the notation.

ttime stepS_tstate at tA_taction at tt+1later time steprindividual rewardS_t+1state at t+1identifiesidentifieslocatesadvances toidentifies
What happens to the notation when the time-step index changes from t to t+1?
Worked example

Reading a Time-Indexed Description

A description says: At time step 4, the agent takes action a and the state being discussed is S_4. Translate the time references into MDP notation.

  1. 1
    Find the time index

    The number 4 identifies the particular time step.

  2. 2
    Find the state notation

    S_4 means the state identified at time step 4.

  3. 3
    Find the action notation

    The action is written as a. If the notation emphasizes that it occurs at time step 4, it can be written as A_4.

Result

The time-indexed forms are S_4 for the state at time step 4 and A_4 for the action at time step 4.

State-Specific Action Sets

A(s) describes the actions available in a particular state s. This is different from a, which denotes one action. The state inside the parentheses matters: A(s) connects the available-action set to the state being considered.

sone stateA(s)actions available in saone actiondetermines the context forcontains an available action
How is a state-specific action set related to one state and one individual action?

Reading an Interaction Sequence

The notation can be read as a sequence of information about an MDP interaction: identify the state being considered, identify an action, identify the reward, and attach a time index when the particular step matters. The symbols do different jobs, so keep the object type and the time reference separate while reading.

S_tstate at tA_taction at trindividual rewardS_t+1state at t+1read action at the same timeread reward notationcontinue to later indexed state
How can the main MDP symbols be read in an ordered interaction description?

Translating Plain Language

Worked example

From Words to Symbols

Translate this generated description: The process is considering one state at time step 2. The action taken at that time is one action from the actions available in that state. The result includes one reward.

  1. 1
    Identify the state

    One state is represented with state notation. Because the state is tied to time step 2, write S_2.

  2. 2
    Identify the action

    One action is represented by a. Because it is tied to time step 2, write A_2.

  3. 3
    Identify the available-action set

    The actions available in the state are represented by A(s).

  4. 4
    Identify the reward

    One reward is represented by r. The set of all possible rewards is represented by R, but the description asks for one reward.

Result

The key symbols are S_2, A_2, A(s), and r.

one statestate objectS_2state at time 2one actionaction objectA_2action at time 2available actionsstate-specific setA(s)actions in state sone rewardreward objectrindividual rewardtranslatetranslatetranslatetranslate
Which parts of a plain-language description correspond to the state, action, reward, time step, and possible-value set?

Common Notation Mistakes

  • Common mistake

    Treating S as one particular state.

    What it looks like

    Reading S as though it means the state at time t.

    Why it fails

    S describes the nonterminal state set, not one individually time-indexed state.

    Do this instead

    Use S_t for a state identified at time t, and use S when discussing the nonterminal state set.

  • Common mistake

    Treating A(s) as one action.

    What it looks like

    Reading A(s) as the action that was taken.

    Why it fails

    A(s) describes the actions available in state s; a denotes one action.

    Do this instead

    Use a for one action and A(s) for the state-specific action set.

  • Common mistake

    Ignoring the time subscript.

    What it looks like

    Treating A_2 and A_5 as interchangeable.

    Why it fails

    The subscript identifies which time step the action belongs to.

    Do this instead

    Read the subscript as part of the meaning: A_2 is the action at time step 2, while A_5 is the action at time step 5.

  • Common mistake

    Using R when the description names one reward.

    What it looks like

    Writing R for a single reward observed in a description.

    Why it fails

    R denotes the set of all possible rewards, while r denotes an individual reward.

    Do this instead

    Use r for one reward and R for the possible-reward set.

Best practice

For every symbol, ask two questions in order: Does it describe one item or a set of possible items? Does it identify a particular time? This simple check separates s from S, a from A(s), r from R, and unindexed notation from forms such as S_t and A_t.

Practice: Decode the Notation

EASY

For each item, identify whether it represents one item, a set of possible items, or an item identified at a particular time: s, S+, A(s), A_7, r, and R. Then write the symbol for the state at time step 3 and the action at time step 3.

Hints
  • Check capitalization and parentheses first.
  • A subscript identifies a time step.
  • Use the notation table to distinguish an individual reward from the reward set.

What do you think happens?

Which symbol best represents the action at time step 7: a, A(s), or A_7?

  • a

  • A(s)

  • A_7

Reveal answer
Answer:

A_7

a identifies an individual action without a time reference, A(s) identifies the actions available in state s, and A_7 identifies the action at time step 7.

The Notation Checklist

  1. 1
    Use s or s′ for individual state notation; use S for nonterminal states and S+ for the inclusive state set.
  2. 2
    Use a for one action and A(s) for the actions available in state s.
  3. 3
    Use r for one reward and R for the set of all possible rewards.
  4. 4
    Use a subscript such as t to identify the time step associated with a state or action, as in S_t and A_t.
  5. 5
    Translate descriptions by checking both dimensions: individual versus set, and unindexed versus time-indexed.

Key Takeaways

  • MDP notation describes states, actions, rewards, and when they occur.
  • Individual objects and sets of possible objects use different notation.
  • A(s) is the set of actions available in state s, while a is one action.
  • Subscripts such as t identify a particular time step.
  • A reliable translation method is to classify each symbol by object type and time reference.

Related Topics

Related concepts

More concepts starting with E