While I was thinking about the Erdős discrepancy problem, the following random walk model arose rather naturally. You fix a positive integer k, and you take a random step of 1 or -1 at each stage, except if that stage is a multiple of k, in which case you get to choose. Your object is to keep the walk as close to the origin as you can.

An obvious strategy is a greedy one: each time you have the choice, if the walk is currently positive you choose -1 and if it's currently negative you choose +1. (Clearly it makes no difference to the outcome what you do if it is zero.) This is like giving your random walk a drift term of size 1/k, but the drift is always directed towards the origin.

A slightly different question would be if you are presented with the entire walk up to kN-1 and you then choose the signs at k, 2k, 3k, ... , Nk, attempting to minimize the maximum distance it ever goes from the origin.

It is not hard to see that it must go at least logarithmically far, since by the time you get to M you will probably have had a run of log M 1s in the random walk, which you can do almost nothing about. I have thought about the problem in a non-rigorous way and it feels to me as though it shouldn't be too hard to prove that by the time you get to M you won't have gone further than $(\log M)^2$ or $(\log M)^3$ or something like that. (The rough argument is that if you look at a run of $k^2$ steps, it won't tend to drift more than about k, and you'll have k steps that you can choose so as to cancel out the drift. That is what usually happens, and the exceptions ought to be exponentially rare, so to speak.)

My main question is this: are these, or something like them, well-known questions? (Or do answers to them follow almost instantly from known results?)