RL in Gridworld, a few questions...

 1. How the Values of Each Cell Are Calculated

In Gridworld, the value of each cell (state) is computed using the Bellman Equation, which balances immediate rewards and future discounted rewards. For a state $s$:

$$V(s)=\underset{a}{\max }\left[\sum _{s^{\prime }}P(s^{\prime }|s,a)\cdot \left(R(s,a,s^{\prime })+\gamma \cdot V(s^{\prime })\right)\right]$$

• $V(s)$: Value of the current state.
• $a$: Action taken in state $s$.
• $P(s^{\prime }|s,a)$: Probability of transitioning to state $s^{\prime }$ after action $a$.
• $R(s,a,s^{\prime })$: Immediate reward for transitioning to $s^{\prime }$.
• $\gamma$: Discount factor (0 ≤ $\gamma$ ≤ 1).

Example:

• If moving "right" from state $s$ leads to state $s^{\prime }$ with reward $R=-0.01$ (step cost) and $V(s^{\prime })=5$, the contribution to $V(s)$ for this action is $-0.01+\gamma \cdot 5$.
• The value $V(s)$ is the maximum of such contributions across all actions.

Values are iteratively updated (e.g., via value iteration) until convergence to the optimal value function.

---

2. Does Gamma Affect Shortest Path Preference?
Yes, $\gamma$ influences path selection if there are step costs (e.g., $R=-0.01$ per step).

• If $\gamma =1$:
  • Future rewards are valued equally with immediate rewards.
  • The agent prioritizes minimizing step costs (e.g., shorter paths) to maximize cumulative rewards.
  • Example: A path with 5 steps (total cost = -0.05) is better than a path with 10 steps (total cost = -0.10), even if both reach the goal.
• If $\gamma <1$:
  • Future rewards are discounted.
  • The agent prefers shorter paths to "lock in" the goal reward sooner (e.g., $10\cdot {\gamma }^5$ > $10\cdot {\gamma }^{10}$).
  • Example: With $\gamma =0.9$, a 5-step path yields $10\cdot 0.9^5\approx 5.9$, while a 10-step path yields $10\cdot 0.9^{10}\approx 3.4$.

If there are no step costs:

• $\gamma$ has no impact on path length, as the total reward is always 10 (goal reward).
• The agent can take any path (long or short) without penalty.

---

Summary:

• Values are computed via the Bellman Equation, incorporating rewards and discounted future values.
• Gamma affects shortest-path preference only if step costs exist. Higher $\gamma$ (closer to 1) still prioritizes shorter paths due to cumulative cost minimization, while lower $\gamma$ amplifies this effect by devaluing delayed rewards.