Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
77,071 characters · 16 sections · 58 citation commands
Reinforcement Learning in High-frequency Market Making
Market making refers to the process where a trader, called a market maker, posts quotes on both sides of the limit order book (LOB) to provide liquidity and generate profit. The main sources of market maker's profit come from capturing the bid-ask spread in the LOB, and meanwhile, they need to avoid holding undesirably large positions to control the inventory risk. It is natural to model the LOB dynamics using stochastic processes, and formulate the market making problem as a stochastic control problem since the target is clearly to maximize the market maker's expected risk-adjust return.
The market making model used in our paper is based on the classical inventory control framework (see, e.g., AmiMen1980HFT_MM, HoStoll1981HFT_MM, AveSto2008HFT_HJB, GCFT2013HFT_MM_HJB_approx, and cartea2014HFT_MM_HJB). Under this framework, the key differences among existing work are on the statistical models of LOB dynamics they adopt. For instance, the seminal work AveSto2008HFT_HJB modeled the price by the Brownian motions and used the controlled Poisson processes to model the market order flows, where the action variable is the quoted price that influences the Poisson rates of market orders; GCFT2013HFT_MM_HJB_approx generalized the model of AveSto2008HFT_HJB by adding the drift term and market impact term in the price dynamics, and made new contributions on the closed-form approximation of the solution; cartea2014HFT_MM_HJB introduced predictable $\alpha$ in the dynamics of price and modeled the market orders by multifactor mutually exciting processes to capture the feedback effects.
The aforementioned papers studied the optimal quoting strategy of a single market maker. In practice, the price competitions among different market markers are also of interest. kyle1984market_game,kyle1985ECTA_market_game,kyle1989RES_market_game introduced informed traders, noisy traders and market makers under the game-theoretical setup, and studied the price competition by explicitly calculating the equilibrium. luo2021HJB_market_making_game considered multiple market makers who are symmetric to each other and have incomplete information, and incorporated the inventory risks in the competitive market making model. Recently, yacMeh2023HFTspeed studied the equilibrium between the high-frequency market maker, who have both speed and informational advantages, with the low frequency trader, and established lots of testable economic implications.
Besides various choices of market making models, an even more important problem is how to solve the optimal strategies. A large amount of previous work, including all of the aforementioned work, adopt the classical Hamilton-Jacobi-Bellman (HJB) equation approach, which could provide closed-form approximate or even exact solutions under some settings. Though the HJB approach is attractive since it can possibly provide analytical solutions and yield lots of insights, it requires that the model of market dynamics is known, which is difficult in reality.
Modern financial markets are increasingly electronic, and this electronification has led to the emergence of big data. Recently, the data-driven machine learning (ML) approaches become more and more popular in finance (see, e.g, XiuKelly2023ML_finance_survey for surveys), and lots of works have applied ML to market making problem. Reinforcement learning (RL, see, e.g., suttonBarto2018RLbook), as a ML technique to solve stochastic control problem, is a natural way to study market making since the market making problem is essentially a stochastic control problem. In general, most RL algorithms are designed to find the optimal policies of the Markov decision process (MDP), which is a discrete-time stochastic control problem, but RL can also solve continuous-time problem after suitable time-discretizations of the model. Compared with the HJB approach, the advantages of RL are that it does not require the knowledge of the underlying model and is able to learn the optimal policy directly from the data. Lots of work has studied the applications of RL on market making (see, e.g., hamblyXuYang2023RL_finance_review and gavsperov2021RLMM_review for surveys). Most of existing works are about methodological research and focus on applying fancy RL algorithms to various market data, however, there is a noticeable lack of study on the theoretical analysis for applying RL algorithm to market making.
Our paper is a pilot to provide a theoretical analysis for the application of RL to high-frequency market making. Our focus is the effects of the sampling frequency on the RL algorithm. We assume that the market maker interacts with the LOB on the discrete-time grid $\{i\Delta\}_{i=0,1,2,...}$ and learns the policy using the standard RL algorithm, e.g., Q-learning. Then we are concerned that, how does the sampling frequency $1/\Delta$ affect the optimal market making strategies and the performance of RL algorithm? Does a smaller $\Delta$, which results in a higher frequency, always lead to better learning results? To answer these questions, we construct a family of MDPs indexed by $\Delta$ to capture the effects of different frequencies, and then analyze the properties of RL algorithm under these MDPs. Our work is also related with high-frequency financial econometrics (see, e.g., yacjacodHFBOOK), where the key target is the statistical estimators constructed by the discrete data of continuous-time processes, but our focus is different and is the learning algorithm in the decision making problem.
In our high-frequency market making setup, we define statistical metrics to characterize the error and the complexity of RL algorithm, and surprisingly, we find an interesting tradeoff between error and complexity when tweaking the values of $\Delta$: As $\Delta$ becomes smaller, the error will be smaller but the complexity will be larger. These two metrics of RL algorithm are of both theoretical and realistic importances. As we will rigorously define later, the error measures the accuracy of our estimation of the expected profit as the RL algorithm iterates, while the complexity measures the transaction costs in some way because every iteration of RL algorithm is actually a quote of market maker. In particular, our theoretical analysis is very general and is applicable to any discretized continuous-time MDP, and thus can be applied to study other high-frequency financial decision making problems, e.g., optimal executions. For practitioners, our results suggest that the choice of sampling frequency should be paid attention and depend on which aspect of the algorithm is given priority to.
Besides the contribution to single-agent case, we establish, under the game-theoretical framework where two market makers have price competitions, the convergence for Nash equilibrium of the discretized model as $\Delta\rightarrow0$, and show that the limiting equilibrium point is identical to the Nash equilibrium of the continuous-time game under uniqueness assumption. We apply the Nash Q-learning algorithm (see, e.g., JMLR2003Nash_Q_learning), which is a multi-agent RL algorithm, to solve the equilibrium for the discretized model. Our results not only provide insight from theoretical sides, but also offer an efficient method to obtain an approximation of equilibrium for continuous-time game. The applications of RL in the competitive market making model has been studied in recent years (see, e.g., ganesh2019RL_multiMM_game,xiong2021MM_collusion,ardon2021RL_multiMM_simulator,cont2022RL_MM_multi_agent,cartea2022MM_game_tick_size,cartea2022QF_MM_game,han2022make_take_fee_RL,wang2023robust_RL_multi,vadori2024multiRL_OTC_simulation). To name a few examples, xiong2021MM_collusion,cont2022RL_MM_multi_agent applied the deep RL approach to study the stochastic game among different market makers, where the competition is modeled as a Nash equilibrium and the tacit collusion is described in terms of Pareto optima. ardon2021RL_multiMM_simulator applied multi-agent RL to establish market simulators and built a new framework where the makers and takers learn simultaneously to optimize their objectives. wang2023robust_RL_multi modeled the market maker and the adversary in a zero-sum game and applied the adversarial RL to learn a strategy that is robust in different adversarial environments. The market making model in cont2022RL_MM_multi_agent is similar to ours and their RL algorithm requires the knowledge of the transition probability model, while the Nash Q-learning algorithm we use is model-free and our focus is the convergence of discretized model to the continuous-time model, which make our paper distinct with theirs.
The rest of our paper is organized as follows. Section (ref) sets up the high-frequency market making model. Section (ref) contructs the time-discretization of the continuous-time model in Section (ref), and shows the convergence of the discretized model as the time increment $\Delta$ goes to zero. Section (ref) provides an upper bound for the sample complexity of Q-learning under the discretized model, and discusses the tradeoff between error and complexity in details. Section (ref) is dedicated to the game theoretical setup where two market makers compete with each other. Section (ref) conducts the numerical studies to validate our theories. Section (ref) concludes. All proofs are in the Appendix.
In this section, we introduce our high-frequency market making model. Before going into the details, we make a general description of our model and explain the motivations. Our model is based on the continuous-time MDP in AveSto2008HFT_HJB (itself following partly HoStoll1981HFMM), where the market order flow is modeled by a controlled Poisson process. The differences are that, first, we model the price dynamics using a controlled continuous-time Markov chain on a finite space, and second, following GCFT2013HFT_MM_HJB_approx, we put a bound $N_{Y}$ to the inventory that the market maker is allowed to have. One common reason for these two constraints is that, they make the state variable of our MDP be on finite space so that it is convenient to analyze the complexity of RL algorithm later. Besides this technical reason, they are also economically sensible. In real LOB, the quoted prices are on a discrete set where the distance between two adjacent price levels is the tick size, and for a single security, the prices which have active quotes and executions are usually within a finite range. Thus, it is natural to assume that the prices are on a equidistant finite space (see, e.g., ContStoikovTalreja10). The bound on inventory is a realistic restriction to control the inventory risk caused by undesirable movements of price.
Denote by $\mathcal{M}_{0}:=(\mathcal{S},\mathcal{A},\mathcal{P},R,\gamma)$ the continuous-time MDP, where $\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space, $\mathcal{P}$ is the transition probability kernel, $R$ is the reward function, and $\gamma$ is the discounted factor. We describe these components as follows.
\paragraph{The state space $\mathcal{S}:=\mathcal{S}_{X}\times\mathcal{S}_{Y}$ and the state variable $S_{t}:=(X_{t},Y_{t})$.}
Denote by $\delta_{P}$ the tick size. Suppose that the limit orders are quoted on the discrete grid $\mathcal{S}_{P}$ defined as \[ \mathcal{S}_{P}:=\{0,\delta_{P},2\delta_{P},...,(N_{P}-1)\delta_{P},N_{P}\delta_{P}\}, \] where $N_{P}\in\mathbb{N}$ is a fixed positive integer. Denote by $X_{t}$ the mid-price. Since the best bid price and the best ask price take values in $\mathcal{S}_{P}$, the mid-price which equals their average should take values in the state space $\mathcal{S}_{X}$ defined as \[ \mathcal{S}_{X}:=\left\{ \frac{k}{2}\delta_{P}\text{ }|\text{ }k=1,2,...,(2N_{P}-1)\right\} . \] Denote by $Y_{i}$ the signed number of inventory held by the agent. Suppose that the state space $\mathcal{S}_{Y}$ of $Y_{t}$ is given by \[ \mathcal{S}_{Y}:=\{-N_{Y},-(N_{Y}-1),...,-2,-1,0,1,2,...,(N_{Y}-1),N_{Y}\}, \] where $N_{Y}\in\mathbb{N}$ is a fixed positive integer. The state variable of the MDP is $S_{t}:=(X_{t},Y_{t})$, i.e., the mid-price of the asset and the inventory holding. The state space $\mathcal{S}:=\mathcal{S}_{X}\times\mathcal{S}_{Y}$ is finite and $|\mathcal{S}|=|\mathcal{S}_{X}||\mathcal{S}_{Y}|=(2N_{P}-1)(2N_{Y}+1)$.
\paragraph{The action space $\mathcal{A}:=\mathcal{S}_{P}\times\mathcal{S}_{P}$ and the action variable $a_{t}:=(p_{t}^{a},p_{t}^{b})$.}
At time $t$, the action variable are the quoted prices $p_{t}^{a}$ and $p_{t}^{b}$ for the limit sell order and limit buy order, respectively, submitted by the agent. Suppose that the volume of every sell order and every buy order is always one unit of the asset, and the agent obey the following restrictions.
Here, the quoted prices $p_{i}^{a}$ and $p_{i}^{b}$ must take values in the set $\mathcal{S}_{P}=\{k\delta_{P}$ $|$ $k=0,1,...,N_{P}\}$.
\paragraph{The transition probability kernel $\mathcal{P}$, the reward function $R$, and the value function $V_{0}^{\pi}(s)$.}
The mid-price $X_{t}$ is a continuous-time Markov chain on state space $\mathcal{S}_{X}$ with the transition rate matrix (a.k.a. Q-matrix) $Q_{X}(a)$ defined as
where the dependence of $\lambda_{k,l}(a)$ on the action variable $a$ models the market impacts of the limit orders from the agents. We propose the following assumption on the rate function $\lambda_{k,l}$.
Denote by $N_{t}^{a}$ (resp. $N_{t}^{b}$) a controlled Poisson process with intensity $\lambda(|p_{t}^{a}-X_{t}|)$ (resp. $\lambda(|p_{t}^{b}-X_{t}|)$), which models the coming flow of the market buy (resp. sell) order at time $t$. The function $\lambda$ should be a monotonically decreasing function, and following AveSto2008HFT_HJB, our choice is $\lambda(d):=\alpha\exp(-\kappa d)$ with the parameters $\alpha,\kappa>0$. As mentioned in AveSto2008HFT_HJB, this function form is motivated from stylized facts of LOB, and the parameters $\alpha$ and $\kappa$ characterize statistically the liquidity of the security.
The inventory value $Y_{t}$ satisfies \[ Y_{t}=-N_{t}^{a}+N_{t}^{b}, \] and the initial values are given by $Y_{t}=N_{t}^{a}=N_{t}^{b}=0$. The value function to be maximized is given by \[ V_{0}^{\pi}(s):=E\left[\left.\int_{0}^{+\infty}e^{-\gamma t}dR_{t}(S_{t},a_{t})\right\vert S_{0}=s\right], \] where $\gamma$ is the discounted factor, and the dynamics of the running reward $R_{t}(S_{t},a_{t})$ is given by
Here, $c>0$ is a constant representing the transaction cost, the function $\psi$ is given by $\psi(y):=\phi y^{2}$ and the parameter $\phi$ measures the risk averse level to the inventory risk. The formulation of the reward $R_{t}(S_{t},a_{t})$ implies that, whenever the agent is allowed to put a sell or buy order, she will always put this order, and her previous orders that have not been executed will not influence the execution probability of her current orders.
In this section, we first introduce the discrete-time market making model, which is a discrete-time approximation of the continuous-time model in Section (ref), and then we show this discretized model is reasonable by proving a set of convergence results. The discrete-time market making model we introduce here will play a key role in studying the effects of sampling frequency later.
In reality, the market maker can only interact with the market in discrete-time grid. Thus, it is natural to study the discrete-time approximation of the continuous-time MDP introduced in Section (ref). For any time increment $\Delta>0$, we consider the discrete-time MDP $\mathcal{M}_{\Delta}:=(\mathcal{S},\mathcal{A},\mathcal{P}_{\Delta},R_{\Delta},e^{-\gamma\Delta})$ defined as follows. Here, $\mathcal{S}$ and $\mathcal{A}$ are the state space and the action space, respectively, and they are the same with those for $\mathcal{M}_{0}=(\mathcal{S},\mathcal{A},\mathcal{P},R,\gamma)$; $\mathcal{P}_{\Delta}$, $R_{\Delta}$, and $e^{-\gamma\Delta}$ are the transition probability kernel, reward function, and discounted factor, respectively.
The state variable is given by $S_{i}:=(X_{i},Y_{i})$, where $X_{i}$ is the mid-price and $Y_{i}$ is the signed number of inventory held by the agent at time $t=i\Delta$. The action variable $a_{i}=(p_{i}^{a},p_{i}^{b})$ is the quoted prices at time $t=i\Delta$. We assume that the agent follows the same rules as we described in Table ((ref)) based on the mid-price $X_{i}$ and the inventory value $Y_{i}$. Then, suppose that the mid-price $X_{i}$ is a Markov chain on state space $\mathcal{S}_{X}$, and the law of $X_{i+1}$ at the $(i+1)$th stage is characterized by the transition probability matrix $P_{X}(\Delta|a)$ defined as \begingroup
\endgroup where $\lambda_{k,l}(a)$ are the same as those of Q-matrix $Q_{X}(a)$ in ((ref)). Suppose that, conditioning on $(S_{i},a_{i})$, $n_{i}^{a}$ and $n_{i}^{b}$ are Bernouli random variables
where $\lambda(d)=\alpha\exp(-\kappa d)$ is the same as that in the intensity function of Poisson processes $N_{t}^{a}$ and $N_{t}^{b}$ in the continuous-time MDP $\mathcal{M}_{0}$, and $P(n_{i}^{a}=1|S_{i},a_{i})$ (resp. $P(n_{i}^{b}=1|S_{i},a_{i})$) is the probability that the sell (resp. buy) limit order is executed. Then the inventory holding $Y_{i+1}$ at the time $(i+1)\Delta$ is given by \[ Y_{i+1}=Y_{i}-n_{i}^{a}+n_{i}^{b}. \]
The value function to be maximized is given by \[ V_{\Delta}^{\pi}(s):=E\left[\left.\sum_{i=0}^{+\infty}e^{-i\gamma\Delta}R_{\Delta}(S_{i},a_{i})\right\vert S_{0}=s\right], \] where, $e^{-\gamma\Delta}$ is the discounted factor, and the reward function $R_{\Delta}(S_{i},a_{i})$ is given by
Here, $c>0$ is the transaction cost and $\psi(y):=\phi y^{2}$ is the same as that appearing in the continuous-time reward function. The $i$th stage of the MDP $\mathcal{M}_{\Delta}$ models what happens at the physical time $t=i\Delta$. The formulation of the reward $R_{\Delta}(S_{i},a_{i})$ implies that, whenever the agent is allowed to put a sell or buy order, she will always put this order, and her previous orders that have not been executed will not influence the execution of her current orders. All interactions between the agent and the market happen on the discrete-time grids $\{i\Delta\}_{i=0,1,2,\ldots}$.
Admittedly, the MDP $\mathcal{M}_{\Delta}$ is not the exact time-discretization of MDP $\mathcal{M}_{0}$. However, the above formulation is not only sensible owing to the convergence results as shown in the next section, but it is also convenient for our theoretical analysis later.
In this section, we show the convergence of the discrete-time MDP $\mathcal{M}_{\Delta}$ to the continuous-time MDP $\mathcal{M}_{0}$ as $\Delta\rightarrow0$ in a suitable sense. As a preparation, we define some relevant notions. For the continuous-time MDP $\mathcal{M}_{0}$, following Section III.9 in FlemingSoner2006book_MDP, we consider the set $\mathcal{U}_{0}$ of admissible policies satisfying that the action $a_{t}$ taken at time $t$ is $\mathcal{F}_{t}$-measurable. In our model, $\mathcal{F}_{t}$ is the $\sigma$-algebra generated by the history $\{S_{t_{1}},a_{t_{1}}\}_{0\leq t_{1}\leq t}$. The optimal value function for $\mathcal{M}_{0}$ is defined as $V_{0}^{*}(s)=\sup_{\pi\in\mathcal{U}_{0}}V_{0}^{\pi}(s)$. For the discrete-time MDP $\mathcal{M}_{\Delta}$, following Section 1.7 in gihSkorohod2012controlled, we consider the set $\mathcal{U}_{\Delta}$ of admissible policies satisfying that the action $a_{i}$ taken at time $i$ is $\mathcal{F}_{i}$-measurable. In our model, $\mathcal{F}_{i}$ is the $\sigma$-algebra generated by the history $\{S_{k}\}_{k=0,1,\ldots,i-1,i}$. The optimal value function for $\mathcal{M}_{\Delta}$ is defined as $V_{\Delta}^{*}(s)=\sup_{\pi\in\mathcal{U}_{\Delta}}V_{\Delta}^{\pi}(s)$. Following kaku1971CTMDP_Bellman and Section 1.7 in gihSkorohod2012controlled, for the MDP $\mathcal{M}_{0}$ (resp. $\mathcal{M}_{\Delta}$), if a policy can be expressed as $a_{t}=\pi(S_{t})$ (resp. $a_{i}=\pi(S_{i})$) where $\pi:\mathcal{S}\rightarrow\mathcal{A}$ is a deterministic mapping, then we say this policy is a stationary Markov policy and we denote this policy as $\pi(\cdot)$.
Theorem (ref) shows the convergence of approximated discrete-time MDP $\mathcal{M}_{\Delta}$ to the continuous-time MDP $\mathcal{M}_{0}$, in terms of both the optimal policy and optimal value functions. An interesting interpretation of (i) is that, since the optimal policies are mappings from the finite state space $\mathcal{S}$ to the finite action space $\mathcal{A}$, we can exactly recover the optimal strategy of continuous-time MDP using discrete-time approximated MDP as long as $\Delta$ is smaller than a threshold.
Compared with the existing literature on the convergence of discrete-time approximation of MDP (see, e.g., BenRobin1982discretizedMDPconverge), one of the advances of our results is that we explicitly give an $O(\Delta)$ upper bound for the distance between the optimal value functions of $\mathcal{M}_{\Delta}$ and $\mathcal{M}_{0}$. To the best of our knowledge, no existing result has established similar results.
In this section, we study the complexity of RL algorithm under the discrete-time MDP $\mathcal{M}_{\Delta}$. Let us briefly review the relevant concepts. For any policy $\pi$, the Q function under policy $\pi$ is defined as \[ Q_{\Delta}^{\pi}(s,a):=E[R_{\Delta}(S_{i},a_{i})+e^{-\gamma\Delta}V_{\Delta}^{\pi}(S_{i+1})|S_{i}=s,a=a_{i}], \] where $V_{\Delta}^{\pi}(s)$ is the value function under policy $\pi$, and $R_{\Delta}(s,a)$ is the stochastic reward function defined in Section (ref). The optimal Q function is given by $Q_{\Delta}^{*}(s,a)=Q_{\Delta}^{\pi_{\Delta}^{*}}(s,a)$, which is the Q function under the optimal policy $\pi_{\Delta}^{*}(\cdot)$.
The RL algorithm we will study is the Q-learning algorithm (see, e.g., Section 6.5 in suttonBarto2018RLbook), which is one of the most popular algorithms. To make our paper self-contained, we explain how Q-learning works in our case as follows. In our model, since the state-action space $\mathcal{S}\times\mathcal{A}$ is finite, the Q-learning algorithm is running in a tabular case. Also, Denote by $Q_{\Delta}^{(n)}(s,a)$ the Q function learned at the $n$th iteration, and denote by $V_{\Delta}^{(n)}(s)=\max_{a\in\mathcal{A}}Q_{\Delta}^{(n)}(s,a)$ the optimal value function learned at the $n$th iteration. The update in each iteration of Q-learning is given by \[ Q_{\Delta}^{(n+1)}(s,a)=Q_{\Delta}^{(n)}(s,a)+\beta^{(n)}(s,a)(R_{\Delta}(s,a)+e^{-\gamma\Delta}\max_{a\in\mathcal{A}}Q_{\Delta}^{(n)}(s^{\prime},a)-Q_{\Delta}^{(n)}(s,a)), \] where $(s,a)$ is the state-action pair at the $n$th iteration, $s^{\prime}$ is the state at the $(n+1)$th iteration and $s^{\prime}$ is the state reached from the state $s$ after taking action $a$, $R_{\Delta}(s,a)$ is the stochastic reward function defined in Section (ref). Following JMLR2003Qcomplexity, we use a polynomial learning rate $\beta^{(n)}(s,a)$ which is given by $\beta^{(n)}(s,a)=(N(s,a,n))^{-\omega}$, where $\omega\in(\frac{1}{2},1)$ and $N(s,a,n)$ is the one plus the number of times, until the $n$th iteration, that we visited the state-action pair $(s,a)$. The initial value of the Q table is set as $Q_{\Delta}^{(0)}(s,a)=C_{0}$ for some constant $C_{0}>0$.
For the exploration method used in Q-learning, we adopt the $\varepsilon$-greedy method (see, e.g., li2012RLcomplexity), which is one of the most popular methods. In our case, the $\varepsilon$-greedy method works as follows: at the $n$th iteration, when the current state is $s$, we take the greedy policy $a^{*}=\text{arg}\max_{a\in\mathcal{A}}Q_{\Delta}^{(n)}(s,a)$ with probability $1-\varepsilon^{(n)}(s)$, otherwise, randomly take an action $a\in\mathcal{A}$ with equal probabilities for each action. Here, $\{\varepsilon^{(n)}(s)\}$ is the sequence of $\varepsilon$ and adapts to the state variable $s$. For the convenience of theoretical analysis, the sequence of $\varepsilon$ we use decays to a nonzero small value $\varepsilon_{0}$ rather than $0$. The details of $\{\varepsilon^{(n)}(s)\}$ are discussed in Section (ref).
The complexity measure we use is the sample complexity (see, e.g., li2012RLcomplexity), which captures the exploration efficiency of RL algorithm. Following JMLR2003Qcomplexity, we define the sample complexity as the number of iteration steps $n$ such that, with probability at least $1-\delta$, it holds $||V_{\Delta}^{(n)}(\cdot)-V_{\Delta}^{*}(\cdot)||\leq\varepsilon_{V}$, where the norm is the same as that in Theorem (ref) and is defined as $||V_{\Delta}^{(n)}(\cdot)-V_{\Delta}^{*}(\cdot)||:=\max_{s\in\mathcal{S}}|V_{\Delta}^{*}(s)-V_{0}^{*}(s)|$. In other words, with high probability, we need at most $n$ iterations to get an estimation of optimal value function within the accuracy level $\varepsilon_{V}$. Our definition of sample complexity is slightly different with that of JMLR2003Qcomplexity in that, we use the value function error while JMLR2003Qcomplexity used the Q function error.
In the high-frequency market making model setup, the sample complexity is closely related with the transaction costs, since every iteration of Q-learning corresponds to a quote of the market maker, which may require a fee in some exchange. The reward functions of our models in Sections (ref) and (ref) do not include the transaction costs due to the convenience of technical analysis. Thus, it is of both theoretical and realistic importance to analyze this sample complexity upper bound, so that we can have a better understanding on how the transaction costs vary with the sampling frequency.
A notable and desirable result in Theorem (ref) is that, the sample complexity upper bound is polynomial, rather than exponential, in all model parameters. In ((ref)), the exponents of $\Delta$ are both negative, since $6-\frac{2}{\omega}-(|\mathcal{S}_{X}|+|\mathcal{S}_{Y}|)(3+\frac{1}{\omega})\leq6-\frac{2}{\omega}-2(3+\frac{1}{\omega})\leq-\frac{4}{\omega}<0$ and $(1-|\mathcal{S}_{X}|-|\mathcal{S}_{Y}|)\frac{1}{1-\omega}\leq-\frac{1}{1-\omega}<0$. From this upper bound, we have the following interpretation: This bound is decreasing in $\Delta$ and will grow to infinity as $\Delta$ goes to zero. So, the larger the quoting frequency $1/\Delta$, the larger the bound of sample complexity. A related work is bayr2023approxRLdiffusion, but their model is different with ours and their focus is to develop learning algorithm for the controlled diffusion process without the background and applications in finance.
Based on the above theoretical results, we now discuss the tradeoff between error and complexity mentioned in the introduction. The learning error is characterized by $||V_{\Delta}^{(n)}(\cdot)-V_{0}^{*}(\cdot)||$, where the groundtruth is the optimal value function $V_{0}^{*}(\cdot)$ of the continuous-time MDP $\mathcal{M}_{0}$ and its estimator is the value function $V_{\Delta}^{(n)}(\cdot)$ learned at the $n$th iteration when running the RL algorithm under the discrete-time MDP $\mathcal{M}_{\Delta}$. The sample complexity is defined as discussed before Theorem (ref). Combining the results in Theorems (ref) and (ref), we have that, when the iteration number $n$ satisfies ((ref)), the learning error can be bounded by \[ ||V_{\Delta}^{(n)}(\cdot)-V_{0}^{*}(\cdot)||\leq||V_{\Delta}^{(n)}(\cdot)-V_{\Delta}^{*}(\cdot)||+||V_{\Delta}^{*}(\cdot)-V_{0}^{*}(\cdot)||\leq\varepsilon_{V}+C_{V}\Delta. \] Regarding the upper bound $\varepsilon_{V}+C_{V}\Delta$ as a metric of the learning error and the upper bound in ((ref)) as a metric of the sample complexity, we have the tradeoff as indicated by the curves in Figure (ref) when the sampling frequency $1/\Delta$ changes and other parameters are fixed.
As the sampling frequency $1/\Delta$ increases, i.e., the time increment $\Delta$ decreases, the learning error goes down while the sample complexity goes up. For practitioners, our results suggest that, the choice of sampling frequency should depend on which aspect of the RL algorithm is primarily concerned. If the accuracy of the estimates of expected profit is given the priority to, then a relatively high sampling frequency is desirable; if the sample complexity that reflects the transaction costs is given more concerns, then it is better to use a relatively low sampling frequency.
In this section, we study the price competition of two market makers in a general-sum game setup which is an extention of the single-player setup discussed previously. Our model is motivated by the game theoretical framework in luo2021HJB_market_making_game and cont2022RL_MM_multi_agent.
Denote by $\text{MM}_{1}$ and $\text{MM}_{2}$ the two market makers. Assume that they share the same state variable $S_{t}=X_{t}$, which is the mid-price of the traded asset. Same with the single-player setup in Section (ref), the state space of $X_{t}$ is $\mathcal{S}_{X}=\{\frac{k}{2}\delta_{P}\text{ }|\text{ }k=1,2,\ldots,(2N_{P}-1)\}$, where $\delta_{P}$ is the tick size. At time $t$, the action variable $a_{t}^{k}$ of $\text{MM}_{k}$ is the quoted prices $a_{t}^{k}=(p_{t}^{a,k},p_{t}^{b,k})$ of her limit sell order and limit buy order, for $k=1,2$. Both of their limit orders are assumed to have one unit of the asset. The mid-price $X_{t}$ is a controlled Markov chain, and its transition rate matrix $Q_{X}(a_{t})$ (a.k.a. Q-matrix) at time $t$ is a function of $a_{t}:=(a_{t}^{1},a_{t}^{2})\equiv(p_{t}^{a,1},p_{t}^{b,1},p_{t}^{a,2},p_{t}^{b,2})$, where $Q_{X}$ is given by
for any $a=(a^{1},a^{2})$. Here, the dependence of $Q_{X}(a)$ on the action variable $a$ captures the price impacts of the limit orders submitted by the market makers.
Next, we specify the execution probability functions that model the intensity of the market orders. It is no longer as simple as $\lambda(|p_{t}^{a}-X_{t}|)$ in the single-player setup, because we need to incorporate the competition between the two market makers now. Denote by $L_{t}^{a,k}=\Gamma^{a,k}(X_{t},p_{t}^{a,1},p_{t}^{a,2})$ (resp. $L_{t}^{b,k}=\Gamma^{b,k}(X_{t},p_{t}^{b,1},p_{t}^{b,2})$) the Poisson rate of the buy (resp. ask) market order flow that executes the ask (resp. buy) limit order of the market maker $\text{MM}_{k}$ for $k=1,2$. We set the functions $\Gamma^{a,k}$ and $\Gamma^{b,k}$ as
where $\min(p^{a,1},p^{a,2})$ (resp. $\max(p^{b,1},p^{b,2})$) is the best ask (resp. bid) prices from the two market makers. We impose the following assumptions on $\Upsilon^{-}$ and $\Upsilon^{+}$.
The economic intuition behind $\Upsilon^{-}$ and $\Upsilon^{+}$ is that, the closer the quoted price is to the mid-price and the best price, the more likely it is that the limit order will be executed (see, e.g., luo2021HJB_market_making_game and cont2022RL_MM_multi_agent for similar specifications of intensity functions). The lower bound on $\Upsilon^{+}$ guarantees the uniformly boundness of the intensity functions $\Gamma^{a,k}$ and $\Gamma^{b,k}$.
Denote by $N_{t}^{a,k}$ (resp. $N_{t}^{b,k}$) the controlled Poisson process with intensity $L_{t}^{a,k}$ (resp. $L_{t}^{b,k}$), which models the flow of the market buy (resp. sell) order at time $t$. The value function of the market maker $\text{MM}_{k}$ is given by \[ V_{0}^{k,\pi^{1},\pi^{2}}(s):=E\left[\left.\int_{0}^{+\infty}e^{-\gamma t}dR_{t}^{k}(S_{t},a_{t}^{1},a_{t}^{2})\right\vert S_{0}=s\right], \] for $k=1,2$, where $\gamma$ is the discounted factor, and the running reward $R_{t}^{k}(S_{t},a_{t}^{1},a_{t}^{2})$ satisfies \[ dR_{t}^{k}(S_{t},a_{t}^{1},a_{t}^{2})=\underset{\text{profit from the sell order}}{\underbrace{(p_{t}^{a,k}-X_{t}-c)dN_{t}^{a,k}}}+\underset{\text{profit from the buy order}}{\underbrace{(X_{t}-p_{t}^{b,k}-c)dN_{t}^{b,k}}.} \] Here, $c>0$ is the transaction cost. We focus on the price competition and simplify the model by ignoring the inventory control in the reward function.
In this two-player game theoretical framework, the target of every market maker is to maximize the value function of herself. Our setup belongs to the class of noncooperative stochastic game (e.g., FilarVrieze2012Book_MDP_game), which means that the two players optimize their individual target and cannot form an enforceable agreement on joint actions. At any time $t$, the agents choose their actions simultaneously and independently. A commonly studied optimality condition is the Nash equilibrium (see, e.g., nash1951AOMequili). Before given the definition, we introduce some relevant notions first. Denote by $\mathcal{P}(\mathcal{A})$ is the space of probability measures on the action space $\mathcal{A}$. For the continuous-time game $\mathcal{G}_{0}$, following GuoHernz2005continuousMDPnonzero_sum_game, we consider the randomized Markov strategies $\Pi_{M}^{1}$, and its subset $\Pi_{s}^{1}$ called the stationary strategies. Formally, $\Pi_{M}^{1}$ is defined as the family of strategies satisfying that, for any $t\geq0$, there exists a mapping $\pi_{t}^{1}:\mathcal{S}\rightarrow\mathcal{P}(\mathcal{A})$, such that for any $(s,a)\in\mathcal{S}\times\mathcal{A}$, the MM1 takes the action $a$ with probability $\pi_{t}^{1}(a|s)$ at time $t$ when the state variable is $S_{t}=s$; $\Pi_{s}^{1}$ is the subset of $\Pi_{M}^{1}$ satisfying that, there exists a mapping $\pi^{1}:\mathcal{S}\rightarrow\mathcal{P}(\mathcal{A})$ such that $\pi_{t}^{1}(a|s)=\pi^{1}(a|s)$ for any $t\geq0$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$. The strategy sets $\Pi_{M}^{2}$ and $\Pi_{s}^{2}$ for $\text{MM}_{2}$ are defined in the same manner.
For each pair $(\pi^{1},\pi^{2})=\{(\pi_{t}^{1},\pi_{t}^{2})\}_{t\geq0}\in\Pi_{M}^{1}\times\Pi_{M}^{2}$, the $(i,j)$-th entry of Q-matrix of the controlled Markov chain $X_{t}$ is defined as $q_{t,ij}(\pi^{1},\pi^{2})=\sum_{a^{1}\in\mathcal{A},a^{2}\in\mathcal{A}}Q_{X,ij}(a^{1},a^{2})\pi_{t}^{1}(a^{1}|s)\pi_{t}^{2}(a^{2}|s)$, where $Q_{X,ij}(a^{1},a^{2})$ is the $(i,j)$-th entry of the Q-matrix $Q_{X}(a^{1},a^{2})$ defined in ((ref)). To guarantee the existence of the process $X_{t}$, we restrict the admissible strategy sets in the classes $\Pi^{1}$ and $\Pi^{2}$ defined as follows: $\Pi^{1}:=\{\pi^{1}\in\Pi_{M}^{1}:q_{t,ij}(\pi^{1},\pi^{2})\text{ is continuous in }t\text{ for any \ensuremath{i,j}}\text{ and }\pi^{2}\in\Pi_{M}^{2}\}$ and $\Pi^{2}:=\{\pi^{2}\in\Pi_{M}^{2}:q_{t,ij}(\pi^{1},\pi^{2})\text{ is continuous in }t\text{ for any \ensuremath{i,j}}\text{ and }\pi^{1}\in\Pi_{M}^{1}\}$. By the uniformly boundness of $Q_{X,ij}(a^{1},a^{2})$, we have that $\Pi_{s}^{k}\subseteq\Pi^{k}\subseteq\Pi_{M}^{k}$ for $k=1,2$.
Following Definition 4.1 in GuoHernz2005continuousMDPnonzero_sum_game, we define the optimality condition for the continuous-time game $\mathcal{G}_{0}$ as follows.
In this section, we introduce the discrete-time stochastic game model $\mathcal{G}_{\Delta}$, which serves as a discrete-time approximation of the continuous-time model $\mathcal{G}_{0}$ in the last section. Then, we show that the Nash equilibrium point of the discrete-time model converges to that of the continuous-time model as the sampling time increment $\Delta$ goes to zero.
Under $\mathcal{G}_{\Delta}$, the two market makers share the same state variable $S_{i}=X_{i}$, which is the mid-price of the traded asset at time $t=i\Delta$. The action variable of the market maker $\text{MM}_{k}$ is $a_{i}^{k}=(p_{i}^{a,k},p_{i}^{b,k})$ of her limit sell order and limit buy order at time $t=i\Delta$, for $k=1,2$. Both of their limit orders are assumed to have one unit of the asset. The transition probability matrix that characterizes the conditional distribution of $X_{i+1}$ given $X_{i}$ is set to be $P_{X}(\Delta|a^{1},a^{2})=I-Q_{X}(a^{1},a^{2})\Delta$, where $I$ is the identity matrix and $Q_{X}(a^{1},a^{2})$ is the Q-matrix defined in ((ref)) for the continuous-time model $\mathcal{G}_{0}$. The execution probability for the ask (resp. buy) limit order of $\text{MM}_{k}$ quoted at time $t=i\Delta$ is given by $\Gamma^{a,k}(X_{i},p_{i}^{a,1},p_{i}^{a,2})\Delta$ (resp. $\Gamma^{b,k}(X_{i},p_{i}^{b,1},p_{i}^{b,2})\Delta$) for $k=1,2$, where $\Gamma^{a,k},\Gamma^{b,k}$ are the intensity functions defined in ((ref)). In other words, if we denote by $n_{i}^{a,k}$ (resp. $n_{i}^{b,k}$) the indicator random variable such that $n_{i}^{a,k}=1$ (resp. $n_{i}^{b,k}=1$) means the ask (resp. buy) limit order of $\text{MM}_{k}$ is executed, then we have that
The value function of the market maker $\text{MM}_{k}$ is given by \[ V_{\Delta}^{k,\pi^{1},\pi^{2}}(s):=E\left[\left.\sum_{i=0}^{+\infty}e^{-i\gamma\Delta}R_{\Delta}^{k}(S_{i},a_{i}^{1},a_{i}^{2})\right\vert S_{0}=s\right], \] for $k=1,2$, where $e^{-\gamma\Delta}$ is the discounted factor, and the running reward $R_{\Delta}^{k}(S_{i},a_{i}^{1},a_{i}^{2})$ is given by \[ R_{\Delta}^{k}(S_{i},a_{i}^{1},a_{i}^{2})=\underset{\text{profit from the sell order}}{\underbrace{(p_{i}^{a,k}-X_{i}-c)n_{i}^{a,k}}}+\underset{\text{profit from the buy order}}{\underbrace{(X_{i}-p_{i}^{b,k}-c)n_{i}^{b,k}}.} \] The constant $c>0$ is the transaction cost. The underlying mechanism of the above time-discretization is the same with that in Section (ref).
Same with the continuous-time game $\mathcal{G}_{0}$, every market maker maximizes the value function of herself, and they choose their actions simultaneously and independently. We will still focus on the Nash equilibrium. We begin by introducing some relevant notions. Following Section 4.1 in FilarVrieze2012Book_MDP_game, we consider the behavior strategies $\Pi_{\Delta}^{k}$ and the stationary strategies $\Pi_{s}^{k}$ defined below. $\Pi_{\Delta}^{k}$ is defined as the family of strategies satisfying that, for any $i\geq0$, the policy $\pi_{i}^{k}\in\mathcal{P}(\mathcal{A})$ taken at time $i$ is measurable w.r.t. the history $(s_{0},a_{0}^{1},a_{0}^{2},\ldots,s_{i-1},a_{i-1}^{1},a_{i-1}^{2},s_{i})$; $\Pi_{s}^{k}$ is a subset of $\Pi_{\Delta}^{k}$ satisfying that the policies are Markov and time invariant, i.e., there exists a mapping $\pi^{k}:\mathcal{S}\rightarrow\mathcal{P}(\mathcal{A})$ such that for any $i\geq0$, the policy $\pi_{i}^{k}$ taken at time $i$ is the randomized policy $\pi^{k}\in\Pi_{\Delta}^{k}$. Here, with a slight abuse of notations, we use the same notation $\Pi_{s}^{k}$ for the stationary strategies in both continuous-time game $\mathcal{G}_{0}$ and discrete-time game $\mathcal{G}_{\Delta}$ since any stationary strategy can be characterized by a single mapping $\pi^{k}:\mathcal{S}\rightarrow\mathcal{P}(\mathcal{A})$ in both cases.
For any pair of behavior strategies $(\pi^{1},\pi^{2})=\{(\pi_{i}^{1},\pi_{i}^{2})\}_{i\geq0}$, we follow the notation convention in Section 4.1 in FilarVrieze2012Book_MDP_game for the reward $R_{\Delta}^{k}(s,\pi_{i}^{1},\pi_{i}^{2})=\sum_{a^{1}\in\mathcal{A},a^{2}\in\mathcal{A}}R_{\Delta}^{k}(s,a^{1},a^{2})\pi_{i}^{1}(a^{1}|s)\pi_{i}^{2}(a^{2}|s)$. Then, following Definition 4.6.1 in FilarVrieze2012Book_MDP_game, we define the Nash equilibrium for the discrete-time stochastic game $\mathcal{G}_{\Delta}$ as follows.
The assumption on the uniqueness of Nash equilibrium in the continuous-time game $\mathcal{G}_{0}$ is necessary. Since nonzero-sum games typically have multiple Nash equilibriums (or no equilibrium), and unlike the zero-sum game, different equilibriums may have different value functions (see, e.g., Abreu1990ECTA_nonzero_sum_games_discrete and sannikov2007ECTA_nonzero_sum_games_continuous).
We now introduce the RL algorithm for the learning of Nash equilibrium. All the learning is conducted in the discrete-time model $\mathcal{G}_{\Delta}$. We adopt the Nash Q-learning algorithm in JMLR2003Nash_Q_learning. In the stochastic game $\mathcal{G}_{\Delta}$, under the pair of strategies $(\pi^{1},\pi^{2})$, the Q function for $\text{MM}_{k}$ is defined as follows, \[ Q_{\Delta}^{k,\pi^{1},\pi^{2}}(s,a^{1},a^{2}):=E[R_{\Delta}^{k}(S_{i},a_{i}^{1},a_{i}^{2})+e^{-\gamma\Delta}V_{\Delta}^{k,\pi^{1},\pi^{2}}(S_{i+1})|S_{i}=s,a_{i}^{1}=a^{1},a_{i}^{2}=a^{2}], \] for $k=1,2$, where $R_{\Delta}^{k}$ is the stochastic reward function of $\text{MM}_{k}$ defined in the previous section, $V_{\Delta}^{k,\pi^{1},\pi^{2}}$ is the value function of $\text{MM}_{k}$, and $e^{-\gamma\Delta}$ is the discounted factor. Indeed, by Theorem 4.6.5 in FilarVrieze2012Book_MDP_game, we have that the Nash equilibrium $(\pi_{\Delta}^{1,*},\pi_{\Delta}^{2,*})\in\Pi_{s}^{1}\times\Pi_{s}^{2}$ in the stationary strategy set satisfies that \[ (\pi_{\Delta}^{1,*}(\cdot|s),\pi_{\Delta}^{2,*}(\cdot|s))=\mathrm{Nash}(Q_{\Delta}^{1,\pi_{\Delta}^{1,*},\pi_{\Delta}^{2,*}}(s,\cdot,\cdot),Q_{\Delta}^{2,\pi_{\Delta}^{1,*},\pi_{\Delta}^{2,*}}(s,\cdot,\cdot)), \] for any $s\in\mathcal{S}$. Here, the operator $\mathrm{Nash}()$ is defined as follows: for any two payoff matrices $Q^{1}(a^{1},a^{2})$ and $Q^{2}(a^{1},a^{2})$ for two players, $\mathrm{Nash}(Q^{1}(\cdot,\cdot),Q^{2}(\cdot,\cdot))$ returns a Nash equilibrium of this two-player static game. Thus, using the above relations between $(\pi_{\Delta}^{1,*},\pi_{\Delta}^{2,*})$ and $(Q_{\Delta}^{1,\pi_{\Delta}^{1,*},\pi_{\Delta}^{2,*}},Q_{\Delta}^{2,\pi_{\Delta}^{1,*},\pi_{\Delta}^{2,*}})$, we reduce the problem of learning equilibrium to the learning of the Q functions at equilibrium. In the Nash Q-learning algorithm, the role of the operator $\mathrm{Nash}()$ is in analogy with the $\arg\max$ operator in the Q-learning algorithm in the single-agent Q-learning algorithm. Denote by $(Q_{\Delta}^{1,i},Q_{\Delta}^{2,i})$ the pair of Q functions learned at the $i$th iteration. The details are shown below.
Under suitable assumptions, the theoretical guarantee for the convergence of the algorithm to the true Nash equilibrium is studied in JMLR2003Nash_Q_learning. In Section (ref), we study numerically the learned strategies and discuss the choice of learning rate $\beta^{i}$ and exploration probability $\varepsilon^{i}$ in details.
In this section, we conduct extensive experiments to validate our results\footnote{All the python codes are available at \href{https://github.com/zyh-pku/Reinforcement-Learning-and-Market-Making}{https://github.com/zyh-pku/Reinforcement-Learning-and-Market-Making}}.
To validate our theory and demonstrate the effects of sampling frequency, we conduct the Monte Carlo simulations in the following setup. \[
\] Here, as defined in the model setup in Sections (ref) and (ref), $N_{P}$ is the number of different price levels minus one, $N_{Y}$ is the maximum absolute number of inventory holding, $\delta_{P}$ is the tick size, $\gamma$ is the discounted factor, $\alpha$ and $\kappa$ determine the intensity function $\lambda(d)=\alpha\exp(-\kappa d)$ of the Poisson process for the market order flow, $\phi$ determines the penalty function $\psi(y):=\phi y^{2}$ for inventory holding, and $c$ is the transaction cost. The Q-matrix of the continuous-time Markov chain for the mid-price $X_{t}$ is set as \[ Q_{X}=\left[
\right]. \] Though our model accommodates the general case where the entries of $Q_{X}$ are functions of action variable $a$, for simplicity here we consider a special case where all entries of $Q_{X}$ are constants. The interpretation is that, the order size of the market maker is small so that the market impact can be ignored and the dynamics of mid-price can be assumed to independent with the action variable. Under this parameter setup, the price space, the mid-price space, and the inventory space are respectively given by \[ \mathcal{S}_{P}:=\{0,\delta_{P},2\delta_{P}\},\text{ }\mathcal{S}_{X}:=\left\{ \frac{1}{2}\delta_{P},\delta_{P},\frac{3}{2}\delta_{P}\right\} ,\text{ and }\mathcal{S}_{Y}:=\{-1,0,1\}. \] To give an example of how the above parameter setup for price dynamics works, we consider the case that the time increment is $\Delta=0.1$. Then, for the discretized model $\mathcal{M}_{\Delta}$, the transition probability matrix of mid-price $X_{i}$ is given by $P_{X}(\Delta|a)=I_{|\mathcal{S}_{X}|}-Q_{X}\Delta$. By calculation we have that, when $X_{i}=\frac{1}{2}\delta_{P}$ (resp. $\frac{3}{2}\delta_{P}$), $X_{i+1}$ goes up (resp. down) to $\delta_{P}$ with probability $1/2$ and stay the same otherwise; when $X_{i}=\delta_{P}$, the probabilities that $X_{i+1}$ goes up, goes down, or stay the same are all equal to $1/3$.
The above parameters and the value of $\Delta$ determine the discrete-time MDP $\mathcal{M}_{\Delta}$. To validate our theory on the effect of $\Delta$, we set $\Delta$ according to the decreasing sequence $\{10^{-1-2k/9}\}_{k=0,1,...,9}$. The optimal value functions $V_{\Delta}^{*}(s)$ and the optimal policies $\pi_{\Delta}^{*}(s)$ of the discrete-time MDP $\mathcal{M}_{\Delta}$ under different values of $\Delta$ can be computed using the Bellman equations. We find that for all the different values of $\Delta$ in our experiment, the optimal policy $\pi_{\Delta}^{*}(s)$ for the discrete-time MDP $\mathcal{M}_{\Delta}$ are all identical to $\pi^{*}(s)=(p_{a}^{*}(s),p_{b}^{*}(s))$ given as follows. For the state variable $s=(x,y)\in\mathcal{S}_{X}\times\mathcal{S}_{Y}$, we have that $p_{a}^{*}(x,y)=2\delta_{P}$ for any $x\in\mathcal{S}_{X}$ and $y=0,1$, $p_{b}^{*}(x,y)=0$ for any $x\in\mathcal{S}_{X}$ and $y=0,-1$; when $y=-1$ (resp. $1$), ask (resp. buy) order is banned and thus $p_{a}^{*}(x)$ (resp. $p_{b}^{*}(x)$) is no need to set. The policy $\pi^{*}(s)$ and the value function $V_{\Delta}^{*}(s)$ with the smallest $\Delta$ in our experiment is an approximate solution to the optimality equations ((ref)) that characterize the continuous-time MDP $\mathcal{M}_{0}$. More precisely, the numerical results show that $\max_{s\in\mathcal{S}}|\gamma V(s)-\max_{a\in\mathcal{A}}(f(s,a)+\sum_{s^{\prime}\in\mathcal{S},s^{\prime}\neq s}\lambda_{s^{\prime}}(s,a)V(s^{\prime})-\lambda(s,a)V(s))|=0.008$, where the difference is small enough and the convergence of optimal and value function in $\mathcal{M}_{\Delta}$ to those in $\mathcal{M}_{0}$ is validated. Since $\pi^{*}(s)$ is a pure strategy, we obtain that the optimal policy of the continuous-time MDP $\mathcal{M}_{0}$ is given by $\pi_{0}^{*}(s)=\pi^{*}(s)$, and the optimal value function $V_{0}^{*}(s)$ is approximated by $V_{\Delta}^{*}(s)$ with the smallest $\Delta$ in our experiment.
In Figure (ref), we plot the optimal value function $V_{\Delta}^{*}(s)$ against $\Delta$. The nine subplots correspond to $V_{\Delta}^{*}(s)$ since the state space $\mathcal{S}=\mathcal{S}_{X}\times\mathcal{S}_{Y}$ is a $3\times3$-dimensional finite space. In each subplot, the dashed line represents the optimal value function $V_{0}^{*}(s)$ of the continuous-time MDP $\mathcal{M}_{0}$ at this state. The dashed line is the value function $V_{\Delta}^{*}(s)$ under the smallest $\Delta$, which is an approximation of $V_{0}^{*}(s)$ as discussed previously. As $\Delta$ goes to zero, the convergence of $V_{\Delta}^{*}(s)$ can be clearly seen from these subplots, since the lines of $V_{\Delta}^{*}(s)$ get closer and closer to the level of $V_{0}^{*}(s)$ as $\Delta$ becomes smaller and smaller. These observations, together with that for the optimal policies mentioned above, demonstrate our results in Theorem (ref) on the convergence of the discrete-time MDP $\mathcal{M}_{\Delta}$ to the continuous-time MDP $\mathcal{M}_{0}$ in terms of the value functions and the policies.
Then we shift the gear to the aspect of the RL method in our theory. For each of the discrete-time MDP $\mathcal{M}_{\Delta}$, we run Q-learning algorithm with $\varepsilon$-greedy exploration as described in Section (ref). Here, the sequence $\{\varepsilon^{(n)}(s)\}$ of the exploration probabilities is set as $\varepsilon^{(n)}(s)=\max(\varepsilon_{0},\rho_{0}\rho^{\left\lfloor N(s,n)/M\right\rfloor })$, where $\varepsilon_{0}$ is the smallest value we permit, $M$ is called the learning epoch, $\rho\in(0,1)$ is the decaying rate of the exploration probability, and $N(s,n)$ is the number of times, until the $n$th iteration, that we visited the state $s$. Under different values of $\Delta$, the hyperparameters $\rho_{0}$, $\rho$, and $M$ vary according to our fine tuning, while the parameter $\varepsilon_{0}$ is fixed at $\varepsilon_{0}=10^{-5}$. For the learning rate $\beta^{(n)}(s,a)=(N(s,a,n))^{-\omega}$ introduced in Section (ref), the hyperparameter $\omega$ we use are close to $0.5$ for all different values of $\Delta$: for $\{\Delta_{k}=10^{-1-2k/9}\}_{k=0,1,...,9}$, we use $\omega=0.501$ when $\Delta=$$\Delta_{2}$, $\Delta_{3}$, and $\Delta_{6}$, and we use $\omega=0.5001$ for all other values of $\Delta$.
To capture the sample complexity using numerical simulations, we record the iteration number $N_{\Delta}$, which is the smallest iteration steps $n$ such that $||V_{\Delta}^{(n)}(\cdot)-V_{\Delta}^{*}(\cdot)||\leq0.1$, when applying the Q-learning algorithm to the discrete-time MDP for each value of $\Delta$.
In Figure (ref), we plot the iteration number $N_{\Delta}$ against $\Delta$, where the x-axis is in logarithmic scale. This increasing trend of the iteration numbers demonstrate our theory about the sample complexity, i.e., the sample complexity upper bound will increase when $\Delta$ decreases. In particular, though the upper bound in Theorem (ref) depends on the hyperparameter $\omega$, the values of $\omega$ we use are all the same regardless the difference smaller than $10^{-2}$. So, the only difference in the upper bound is the values of $\Delta$ and the upward trend in Figure (ref) does validate Theorem (ref).
First, we examine the convergence of Nash equilibrium. We start with the following setup. For the intensity functions $\Gamma^{a,k}$ and $\Gamma^{b,k}$, their building blocks $\Upsilon^{-}$ and $\Upsilon^{+}$are set to \[ \Upsilon^{-}(d)=\alpha\exp(-\kappa d)\text{ and }\Upsilon^{+}(d)=\frac{1}{2}\sqrt{1+3\exp(-\kappa d)}. \] This choice of intensity functions connects to the single-agent case in the following sense: when the two market makers always quote the same prices, i.e., $p_{t}^{1,a}=p_{t}^{2,a}=p_{t}^{a}$ and $p_{t}^{1,b}=p_{t}^{2,b}=p_{t}^{b}$, the intensity of market flows they will receive is exactly same with the single-agent case because by calculations we have that \[ \Gamma^{a,k}(x,p^{a},p^{a})=\frac{\Upsilon^{-}(|p^{a}-x|)}{\Upsilon^{+}(0)}=\lambda(|p^{a}-x|)\text{ and }\Gamma^{b,k}(x,p^{b},p^{b})=\frac{\Upsilon^{-}(|p^{b}-x|)}{\Upsilon^{+}(0)}=\lambda(|p^{b}-x|). \] We set the model parameters the same as the setup in the single-agent case.
The above parameters and the value of $\Delta$ determine the discrete-time game $\mathcal{G}_{\Delta}$. To validate our theory on the effect of $\Delta$, we set $\Delta$ according to the decreasing sequence $\{10^{-1-2k/9}\}_{k=0,1,...,9}$. For the true Nash equilibrium, we solve it through value iteration following the same manner of Bellman iteration in the single-agent case. In this example, the model is symmetric w.r.t. $\text{MM}_{1}$ and $\text{MM}_{2}$, and thus the strategies and the value functions of $\text{MM}_{1}$ and $\text{MM}_{2}$ should be the same with each other, i.e., $\pi_{\Delta}^{1,*}=\pi_{\Delta}^{2,*}$ and $V_{\Delta}^{1,\pi_{\Delta}^{1,*},\pi_{\Delta}^{2,*}}(s)=V_{\Delta}^{2,\pi_{\Delta}^{1,*},\pi_{\Delta}^{2,*}}(s)$. Also, under our current setup, we find from the numerical results that there is exactly one Nash equilibrium for $\mathcal{G}_{\Delta}$ under different values of $\Delta$.
The convergence of Nash equilibrium is validated by the numerical results as follows. First, we find that all the Nash equilibriums computed in $\mathcal{G}_{\Delta}$ under different values of $\Delta$ are exactly the same with each other. Second, the convergence of the value function $V_{\Delta}^{k,\pi_{\Delta}^{1,*},\pi_{\Delta}^{2,*}}(s)$ at Nash equilibrium is illustrated in Figure (ref). These equilibrium points under $\mathcal{G}_{\Delta}$ are all equal to a pure strategy $\pi_{0}^{*}(s)$, i.e., $\pi_{\Delta}^{1,*}(s)=\pi_{\Delta}^{2,*}(s)=\pi_{0}^{*}(s)=(p_{a}^{*}(s),p_{b}^{*}(s))$, where $p_{a}^{*}(\frac{1}{2}\delta_{P})=p_{a}^{*}(\delta_{P})=p_{a}^{*}(\frac{3}{2}\delta_{P})=2\delta_{P}$ and $p_{b}^{*}(\frac{1}{2}\delta_{P})=p_{b}^{*}(\delta_{P})=p_{b}^{*}(\frac{3}{2}\delta_{P})=0$. The strategy is the reaction of the market maker to the state variable $s$ which is the mid-price in the state space $\mathcal{S}_{X}=\{\frac{1}{2}\delta_{P},\delta_{P},\frac{3}{2}\delta_{P}\}$. The interpretation of the pure strategy $\pi_{0}^{*}(s)=(p_{a}^{*}(s),p_{b}^{*}(s))$ is that, no matter what level of mid-price is, both $\text{MM}_{1}$ and $\text{MM}_{2}$ will quote at the highest ask price $2\delta_{P}$ (resp. lowest bid price $0$) to maximize their expected profit. In particular, this special optimal strategy is due to the simple setup we are currently studying, and the optimal strategy should be much more complicated and variant with different states in general setup, e.g., the dimension of state space $\mathcal{S}_{X}$ is high.
Besides the identity among $(\pi_{\Delta}^{1,*}(s),\pi_{\Delta}^{2,*}(s))$ under different $\Delta$ and the convergence trend of $(V_{\Delta}^{1,\pi_{\Delta}^{1,*},\pi_{\Delta}^{2,*}}(s),V_{\Delta}^{2,\pi_{\Delta}^{1,*},\pi_{\Delta}^{2,*}}(s))$ shown in Figure (ref), the convergence results in Theorem (ref) are further validated by the findings below. We find that, the strategy pair $(\pi_{0}^{1}(s),\pi_{0}^{2}(s))=(\pi_{0}^{*}(s),\pi_{0}^{*}(s))$ and the value function pair $(V_{0}^{1}(s),V_{0}^{2}(s))=(V_{\Delta}^{1,\pi_{\Delta}^{1,*},\pi_{\Delta}^{2,*}}(s),V_{\Delta}^{2,\pi_{\Delta}^{1,*},\pi_{\Delta}^{2,*}}(s))$ with the smallest $\Delta$ in our experiment is an approximate solution to the optimality equations ((ref))--((ref)) that characterize the Nash equilibrium in continuous-time game $\mathcal{G}_{0}$. More precisely, the numerical results show that $\max_{s\in\mathcal{S}}|\gamma V_{0}^{1}(s)-\max_{a\in\mathcal{A}}\bigl(r^{1}(s,a,\pi_{0}^{*})+\sum_{s^{\prime}\in\mathcal{S}}\lambda(s^{\prime}|s,a,\pi_{0}^{*})V_{0}^{1}(s^{\prime})\bigr)|=0.057$ and $\max_{s\in\mathcal{S}}|\gamma V_{0}^{2}(s)-\max_{a\in\mathcal{A}}\bigl(r^{2}(s,\pi_{0}^{*},a)+\sum_{s^{\prime}\in\mathcal{S}}\lambda(s^{\prime}|s,\pi_{0}^{*},a)V_{0}^{2}(s^{\prime})\bigr)|=0.057$, where the difference is small enough and the convergence of Nash equilibrium strategy and value function in $\mathcal{G}_{\Delta}$ to those in $\mathcal{G}_{0}$ is validated.
Then, we shift the gear to the aspect of the RL method in our theory. Under the discrete-time game $\mathcal{G}_{\Delta}$ with time increment $\Delta=0.1$, we run Nash Q-learning algorithm with $\varepsilon$-greedy exploration as described in Algorithm (ref) in Section (ref). Here, the sequence $\{\varepsilon^{n}(s)\}$ of the exploration probabilities is set as $\varepsilon^{n}(s)=\max(\varepsilon_{0},\rho_{0}\rho^{\left\lfloor N(s,n)/M\right\rfloor })$, where $\varepsilon_{0}$ is the smallest value we permit, $M$ is called the learning epoch, $\rho\in(0,1)$ is the decaying rate of the exploration probability, and $N(s,n)$ is the number of times, until the $n$th iteration, that we visited the state $s$. The learning rate sequence $\{\beta^{n}(s,a^{1},a^{2})\}$ is similarly set as $\beta^{n}(s,a^{1},a^{2})=\eta_{0}\eta^{\left\lfloor N(s,a^{1},a^{2},n)/M_{b}\right\rfloor }$, where $N(s,a^{1},a^{2},n)$ is the number of times, until the $n$th iteration, that we visited the state action pair $(s,a^{1},a^{2})$.
In our experiment, the hyperparameters $\varepsilon_{0}$, $\rho_{0}$, $\rho$, $M$, $\eta_{0}$, $\eta$, and $M_{b}$ are tuned to guarantee the convergence of the Nash Q-learning algorithm. We plot in Figure (ref) how the learning errors of value functions and policies decay w.r.t. the iteration steps of the Nash Q-learning algorithm. The value function error and the policy error are given by $\max_{s\in\mathcal{S}}|V_{\Delta}^{k,i}(s)-V_{\Delta}^{k,\pi_{\Delta}^{1,*},\pi_{\Delta}^{2,*}}(s)|$ and $\max_{s\in\mathcal{S}}||\pi_{\Delta}^{k,*}(\cdot|s)-\pi_{0}^{k,*}(\cdot|s)||$, respectively, where $||\pi(\cdot)-\pi^{\prime}(\cdot)||=\max_{a\in\mathcal{A}}|\pi(a)-\pi^{\prime}(a)|$ for any $\pi,\pi^{\prime}\in\mathcal{P}(\mathcal{A})$. The learned strategy is exactly same with the true strategy, i.e., the policy error is zero, and the value function error ends with $(0.09,0.05)$, demonstrating the effectiveness of the Nash Q-learning algorithm. In Figure (ref), we use red color to mark the steps that have nonzero policy error. We find that, the policy error often follows from a rise in the value function error, e.g., around 400th and 800th steps in Figure (ref) (left); when the rise in value function error is small, the RL algorithm can still perfectly learn the true policy, e.g., around 800th steps in Figure (ref) (right).
In this paper, we provide a novel and comprehensive theoretical analysis for RL algorithm in high-frequency market making problem. We target the effects of sampling frequency on the RL method, and find an interesting tradeoff between the accuracy and the complexity of RL algorithm when changing the frequency. Both of these two metrics are of realistic importance because, the error captures the accuracy of our estimation of the expected profit and the complexity measures the total transaction costs in some way as every iteration of RL algorithm corresponds to a quote of market maker. Furthermore, we extend our model to study the price competitions for multiple market makers under the game theoretical framework. We establish the convergence of Nash equilibrium from discretized model to continuous-time model, and apply the Nash Q-learning to solve the equilibrium. Our theory is applicable to any discretized continuous-time Markov decision process, and thus can be used to study many other high-frequency financial decision making problems, e.g., optimal executions. Our results also provide a guide for practitioners on the choice of sampling frequency, which should depend on what aspect of the algorithm is primarily concerned by them.
While the current scope of our theory is considerably wide-ranging, it is possible to further widen it and there are lots of topics that are worth pursuing. For instance, how to generalize our theory for more complex market making models and more sophisticated RL methods, e.g., deep RL algorithm? Is it possible to sharpen the sample complexity upper bound or even make it tight, such that we have a better characeterization for the effects of sampling frequency? What will happen to our theoretical analysis if we switch to the multi-asset case where multiple assets can be traded in the market? Among many directions, these topics can be investigated in future research.