Navigation up a sensory gradient is one of the simplest behaviours, and the simplest strategy is run and tumble. But some organisms use other strategies, such as reversing direction or turning by some angle. Here we ask what drives the choice of strategy, which we frame as maximising up-gradient speed using a given amount of sensory information per unit time. We find that, without directional information on which way to turn, behavioural strategies which make sudden turns perform better than gradual steering. We see various transitions where a different strategy becomes optimal, such as a switch from reversing direction to fully re-orienting tumbles as more information becomes available. And, among more complex re-orientation strategies, we show that discrete turn angles are best, and see transitions in how many such angles the optimal strategy employs.