Why does a negative reward for every step really encourage the agent to reach the goal as quickly as possible? If we shift the rewards by any constant (which is a type of reward shaping), the optimal state-action value function (and so optimal policy) does not change. The proof of this fact can be found here.
If that's the case, then why does a negative reward for every step encourage the agent to quickly reach the goal (which is a specific type of behavior/policy), given that such a reward function has the same optimal policy as the shifted reward function where all rewards are positive (or non-negative)?
More precisely, let $s^*$ be the goal state, then consider the following reward function
$$
r_1(s, a)=
\begin{cases}
-1, &amp; \text{ if }  s \neq s^*\\
0, &amp; \text{ otherwise}
\end{cases}
$$
This reward function $r_1$ is supposed to encourage the agent to reach $s^*$ as quickly as possible, so as to avoid being penalized.
Let us now define a second reward function as follows
\begin{align}
r_2(s, a) 
&amp;\triangleq r_1(s, a) + 1\\
&amp;=
\begin{cases}
0, &amp; \text{ if }  s \neq s^*\\
1, &amp; \text{ otherwise}
\end{cases}
\end{align}
This reward function has the same optimal policy as $r_1$, but does not incentivize the agent to reach $s^*$ as quickly as possible, given that the agent does not get penalized for every step. So, in theory, $r_1$ and $r_2$ lead to the same behavior. If that's the case, then why do people say that $r_1$ encourage the agents to reach $s^*$ as quickly as possible? Is there a proof that shows that $r_1$ encourages a different type of behaviour than $r_2$ (and how is that even possible given what I have just said)?
Your examples are equivalent. But it is possible to find a constant yielding  a different optimal policy.
Your examples are absolutely equivalent. The agent maximizes the reward, and only way to do so is by reaching $s^*$.
Consider $r_3$ :
$$
r_3(s, a)=
\begin{cases}
1, &amp; \text{ if }  s \neq s^*\\
2, &amp; \text{ otherwise}
\end{cases}
$$
With a sufficiently large $\gamma$, moving infinitely without reaching $s^*$ is now the optimal solution.
For the generic case
$$
r_4(s, a)=
\begin{cases}
\alpha, &amp; \text{ if }  s \neq s^*\\
\beta, &amp; \text{ otherwise}
\end{cases}
$$
the threshold is found by comparing the results of the series $\alpha + \alpha^2 + \alpha^3 + ... + \alpha^{t_m}$, where $t_m$ is the maximum episode length, and $\alpha + \alpha^2 + \alpha^3 + ... + \alpha^{t^*}$, where $t^*$ is the length of the episode following the fastest policy.
In the example of $r_3$, it is trivial to find examples where the fastest policy isn't optimal. Imagine a race, the agent starts on the left and gets either $\alpha$ or $\beta$ points, depending on where it is. With $\gamma = 0.9$ and no time-limit (infinite episodes) the optimal policy is  to move randomly, but in the second-to-last house, avoid the goal state. With $\gamma = 0.1$, the optimal policy is to move randomly (not really, probably there would be a slight advantage in moving right), but in the second-to-last house, enter the goal.