You can solve the problem via dynamic programming. For $n\in\{1,\dots,t\}$, let $V(n)$ be the minimum expected number of steps starting from $n$. Then $V(1)=0$ and otherwise $$V(n) = 1+\min\left(\frac{1}{n}\sum_{k=1}^n V(k), V(n-1)\right).$$

Because $V(n)$ appears on both sides, you cannot just iterate the recursion. Instead, you can use linear programming as follows. The problem is to maximize $\sum_{n=1}^t V(n)$ subject to linear constraints \begin{align} V(1) &= 0 \\ V(n) &\le 1 + \frac{1}{n}\sum_{k=1}^n V(k) \\ V(n) &\le 1 + V(n-1) \\ \end{align} Here's a plot of $V(n)$ for $n\in\{1,\dots,1000\}$:

You can solve the problem via dynamic programming. For $n\in\{1,\dots,t\}$, let $V(n)$ be the minimum expected number of steps starting from $n$. Then $V(1)=0$ and otherwise $$V(n) = 1+\min\left(\frac{1}{t}\sum_{k=1}^t V(k), V(n-1)\right).$$

Because $V(n)$ appears on both sides, you cannot just iterate the recursion. Instead, you can use linear programming as follows. The problem is to maximize $\sum_{n=1}^t V(n)$ subject to linear constraints \begin{align} V(1) &= 0 \\ V(n) &\le 1 + \frac{1}{t}\sum_{k=1}^t V(k) \\ V(n) &\le 1 + V(n-1) \\ \end{align} Here's a plot of $V(n)$ for $n\in\{1,\dots,1000\}$:

In particular, $$V(n)= \begin{cases} n-1 &\text{for $n \le 45$}, \\ 44+2/9 &\text{otherwise}. \\ \end{cases}$$