State-Value Function Bellman Update

In Reinforcement Learning, an agent learns to make optimal decisions by interacting with an environment modeled as a Markov Decision Process (MDP). A fundamental component of solving MDPs is computing the state-value function V(s), which quantifies the expected cumulative reward an agent can obtain starting from state s and following an optimal policy.

The Bellman Optimality Equation provides a recursive relationship that defines the optimal value function. The key insight is that the optimal value of any state equals the best action's immediate reward plus the discounted value of the resulting state. Mathematically:

$$V(s) = \max_{a} \sum_{s', r} P(s', r | s, a) \cdot [r + \gamma \cdot V(s') \cdot (1 - \text{terminal})]$$

Where:

• V(s) is the value of state s
• a represents an action available in state s
• P(s', r | s, a) is the probability of transitioning to state s' and receiving reward r when taking action a in state s
• γ (gamma) is the discount factor (0 < γ ≤ 1) that weights the importance of future rewards
• terminal is a flag indicating whether the transition leads to a terminal state (episode ends)

Value Iteration Algorithm: Value iteration is an iterative algorithm that computes optimal state values by repeatedly applying the Bellman update to all states until convergence. One iteration (or "sweep") updates every state's value based on the current value estimates of all states.

MDP Transition Structure: The environment is specified as a list of transition dictionaries. For each state s, transitions[s] is a dictionary where:

• Keys are action indices (integers)
• Values are lists of tuples: (probability, next_state, reward, is_terminal)

Each tuple represents a possible outcome when taking that action, with the probability of that outcome occurring, the resulting state, the immediate reward received, and whether this ends the episode.

Your Task: Implement a function that performs one complete iteration of value iteration using the Bellman equation. Given the current state-value estimates V, transition dynamics, and discount factor γ, compute and return the updated value function.

Important Notes:

• When a transition leads to a terminal state (is_terminal = True), the future discounted value should be 0 (the episode ends, so no future rewards can be collected)
• For each state, compute the maximum expected value across all available actions
• Use NumPy for efficient numerical computations