Expected Immediate Reward of a Policy

1. Background Knowledge

In a Markov Decision Process (MDP), an agent interacts with an environment by selecting actions based on its current state. A policy $\pi$ defines the agent's behavior: for each state $s$, it specifies a probability distribution over actions. Formally, $\pi(a \mid s)$ is the probability of taking action $a$ in state $s$, and these probabilities must sum to 1 for all actions in that state.

The expected immediate reward $r^\pi(s)$ represents the average reward the agent can expect to receive in state $s$ when following policy $\pi$. It is computed as a weighted sum of the rewards for each action, where the weights are the policy's action probabilities. This concept is foundational to Bellman equations, which relate the value of a state to the expected rewards and future values of successor states. Understanding this simple expectation is the first step toward computing state values, action values, and ultimately optimal policies.

2. Algorithm Approach

This problem is a straightforward application of the dot product between two vectors: the policy vector (probabilities) and the reward vector (expected rewards per action). The algorithm pattern is:

1. Validate that the policy is a valid probability distribution (non-negative, sums to 1).
2. Compute the element-wise product of the policy and reward vectors.
3. Sum the resulting products to obtain the expected reward.

This is essentially computing $\sum_a \pi(a \mid s) \cdot r(s, a)$, which is the definition of the expected value of a discrete random variable.

3. Step-by-Step Strategy