States and Actions

State Space

A state $s \in S$ captures everything the agent needs to make a decision. In practice, states can be:

• Discrete — e.g., grid positions in a maze, board configurations in a game
• Continuous — e.g., joint angles and velocities of a robot, pixel values in an image

The key requirement is the Markov property: the state must contain enough information to predict the future without knowing the past.

Observation vs. State

In many real-world problems, the agent doesn’t observe the full state. When the observation $o_t$ is a partial view of $s_t$, we have a Partially Observable MDP (POMDP). Most practical deep RL algorithms treat observations as if they were states.

Action Space

The action space $A$ defines what the agent can do:

• Discrete actions — e.g., move left/right/up/down, select a token from vocabulary
• Continuous actions — e.g., torque applied to a joint, steering angle

For language models, the action space is the vocabulary — at each step, the model selects a token.

Policy

The policy $\pi_\theta(a \mid s)$ maps states to a distribution over actions. It’s parameterized by $\theta$ (e.g., the weights of a neural network).

• Deterministic policy: $a = \mu_\theta(s)$
• Stochastic policy: $a \sim \pi_\theta(\cdot \mid s)$

In deep RL, the policy is typically a neural network. For language models, the policy is the model — it outputs a probability distribution over the next token given the context.

Worked Example

Consider 5 candidate actions with logits $z = [0.5, 1.2, -0.3, 0.8, 0.0]$. With temperature $\tau = 1$:

$$\pi(a_i) = \frac{\exp(z_i)}{\sum_j \exp(z_j)} \approx [0.180, 0.363, 0.081, 0.244, 0.132]$$

With $\tau = 0.2$ (sharper): action 1 takes essentially 100% of the mass. With $\tau = 3$ (smoother): probabilities flatten toward uniform $\approx 0.20$ each. The same logits, very different policies — temperature is one of the simplest exploration knobs.

Interactive: Build a Softmax Policy

Slide the logits or the temperature and watch the resulting categorical distribution. This is exactly the shape of $\pi_\theta(a \mid s)$ for an LLM at one decoding step, just over 5 actions instead of 50,000.

Common misconception: “A bigger network = a smarter policy.”

The capacity of the network sets an upper bound on what the policy can learn, but the state representation is what determines whether learning is even possible. If $s_t$ doesn’t contain a Markov sufficient statistic, no policy network — however deep — can learn the optimal action. A toy example: try training a feed-forward net on Atari from a single frame. It will fail not because the net is too small but because velocity is not present in one frame. Adding 4 stacked frames (the original DQN trick) makes the same net suddenly work. State design is RL design.

The Agent-Environment Loop

At each timestep $t$:

1. Agent observes state $s_t$
2. Agent samples action $a_t \sim \pi_\theta(\cdot \mid s_t)$
3. Environment transitions to $s_{t+1} \sim P(\cdot \mid s_t, a_t)$
4. Agent receives reward $r_t = R(s_t, a_t)$

This loop repeats until a terminal state is reached (episodic) or continues forever (continuing).