I'm not sure whether my solution is correct or not, but I'll write it down anyway. Let $a$ be the least non-$d$th power modulo $p$. Let $b$ be the least integer such that $ab > p$ and let $ab=p+k$. Since $p$ is a prime, obviously $0 < k < a$. Hence $ab \equiv k$ is a $d$th power and $b$ is a non-$d$th power since $a$ is also a non-$d$th power. Thus $a \le b < p/a + 1$ and therefore $a < \sqrt{p} + 1$. Now $\log r = \epsilon - \frac{1}{\gcd (d,p-1)} > -\frac{1}{2}$ and hence $r > \frac{1}{\sqrt{e}} > \frac{1}{2}$. Therefore there exists a non-$d$th power modulo $p$ less that $p^r$.