Q-Learning Grid-World

An agent learns to navigate an environment not by being handed a map, but by exploring, acting, and observing rewards. In reinforcement learning, the environment is modeled as a Markov Decision Process (MDP).

The agent's goal is to learn a policy—a rule for what action to take in every state—that maximizes its total future reward. Since future rewards are uncertain and delayed, the agent learns $Q(s, a)$, the expected cumulative reward for taking action $a$ in state $s$.

The Bellman Update

The agent uses the Bellman equation to update its Q-values iteratively as it explores:

$$Q(s, a) \leftarrow Q(s, a) + \alpha \left[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \right]$$

• $r$ is the immediate reward received.
• $\gamma$ is the discount factor, which determines how much the agent cares about future rewards versus immediate ones.
• $\alpha$ is the learning rate, controlling how much new information overwrites old information.
• $\max_{a'} Q(s', a')$ is the agent's current estimate of the best possible future value from the next state $s'$.

By continually exploring using an $\epsilon$-greedy strategy (picking a random action with probability $\epsilon$ to discover new paths) and updating its Q-values, the agent eventually discovers the optimal policy. The optimal action in any state is simply the one with the highest Q-value: $\arg\max_a Q(s, a)$.