We characterise profit-maximising operating strategies, over some time horizon [0, T], for an energy store which is trading in an arbitrage market. Our theory allows for leakage, operating inefficiencies and general cost functions. In the special case where the operating cost of a store depends only on its instantaneous power ouput (or input), we present an algorithm to determine the optimal strategies. A key feature is that this algorithm is localised in time, in the sense that the action of the store at a time t ∈ [0, T] only requires information about electricity prices over some subinterval of time [t, τ ] ⊂ [t, T].