Trading algorithms with storage limits achieve near optimal profits
Trading with the STARS: Algorithm Design & Spectrum of Fundamental Limits for Trading with Storage
Data Structures and AlgorithmsComputer Science and Game Theory
Summary
This paper looks at how to make the best buy, sell, or hold decisions when trading a product with limits on storage, using prices that come from a known range but change over time. The authors show how the difficulty of this task depends on how prices cluster around the middle value, and they prove that some amount of error in decision-making is unavoidable. They introduce an algorithm called STARS that tries out many future price possibilities to decide what to do next. STARS performs very well and nearly matches the best possible decisions across a wide variety of price patterns.
What this means in practice
- •For algorithmic trading teams: Design trading systems that optimize decisions under limited inventory and known price distributions using simulated future price scenarios.
- •For energy storage operators: Improve buying and selling schedules for energy stored in batteries when future prices follow known statistical patterns.
Authors
Jerry Anunrojwong, Akshit Kumar, Rachitesh Kumar
Abstract
We study an online trading problem where a trader, given a sequence of i.i.d. prices drawn from a known distribution $F$ on $[0,1]$, must make irrevocable buy, sell, or hold decisions subject to storage constraints. We investigate achievable algorithmic performance measured in terms of regret, the difference between the expected profit of the hindsight optimal policy that knows the entire price sequence and an online algorithm. We analyze finite atomic and continuous distributions characterized by their local behavior around the median which we capture using a parameter $β$. The parameter $β$ quantifies how the mass of prices accumulates around the distribution median. We identify a new driver of algorithmic performance, demonstrating that median gaps coupled with an initial inventory level of zero can force regret scaling of $Ω(T^{(β+ 1)/(2β+4)})$ --- establishing a novel spectrum of fundamental limits on algorithmic performance. We then study STARS, short for Storage Trading by Averaging Repeatedly across multiple Scenarios, which simulates possible future price scenarios to approximate the value-to-go function and make buy/sell/hold decisions. We show that STARS obtain near-optimal algorithmic performance (upto poly-logarithmic factors) across a broad range of distributions. In particular, it achieves $O(\log T)$ regret for finite atomic prices, $\widetilde{O}(T^{β/(2β+2)})$ for continuous distributions without a median gap and $\widetilde{O}(T^{(β+1)/(2β+4)})$ for continuous distributions with a median gap for $β\geq 0$.