Consider the following problem which I give a "physical" marbles/tubes description of -- the formal description is easy to obtain from this "physical" description.
Moving marbles between tubes. Let $N =2^n$ be a large positive integer, and $f(n)$ a sublinear function of $n$ such as $\sqrt{n}$ or $\log n$. Suppose you are an automaton performing the following simple task: there are three tubes, labeled $A, B, C$ that marbles can be placed into. Tubes $A$ and $B$ start empty while tube $C$ contains $N$ marbles all stacked in a tower. A step involves picking a marble off from the top of tube $C$ (and $B$ if non-empty), and placing it at the bottom of tube $A$: thus if tube $A$ already has $k$ marbles in it, we must dump out all these marbles and place the new marble at the bottom -- this operation has a cost $k$. Every step we are required to place one marble from Tube $C$ and one marble from Tube $B$ (if non-empty) at the bottom of tube $A$. But during a step we may also remove all $k$ marbles in $A$ from previous steps, and place them all into tube $B$, incurring a cost of $(k+l)f(k+l)$ if Tube $B$ already contains $l\geq 0$ marbles, or place them all back into tube $C$, incurring a cost of $Nf(N)$. Doing so allows us to "start fresh."
The problem, then, is as follows:
Problem. What is the optimal strategy for moving marbles between the tubes if we want to minimize the average cost over $N$ steps? Can we lower bound this average cost?