Randomising the length of the first step will improve on the constant factor by about 2. Similar analysis to the non-adversarial case, and with the same ETA I just added to my earlier comment.
If you make the run lengths increase exponentially instead of linearly then you get O(k) unconditionally.
Related to: Half-assing it with everything you've got; Wasted motion; Say it Loud.
Once upon a time (true story), I was on my way to a hotel in a new city. I knew the hotel was many miles down this long, branchless road. So I drove for a long while.
After a while, I began to worry I had passed the hotel.
So, instead of proceeding at 60 miles per hour the way I had been, I continued in the same direction for several more minutes at 30 miles per hour, wondering if I should keep going or turn around.