A* Tree Search for Portfolio Management

Lei XuarXiv 2019 · arXiv

TL;DR

This paper introduces "A Tree Search" (ATS), a novel deep reinforcement learning framework that combines A search with Monte Carlo Tree Search (MCTS) for portfolio management. ATS aims to improve decision-making by prioritizing optimal nodes in the search tree, leading to more robust and profitable trading strategies compared to existing RL methods.

What Problem Does This Paper Address?

Traditional supervised learning methods struggle in financial domains due to the lack of clear labels and the dynamic, complex nature of markets. While reinforcement learning (RL) offers a promising alternative by learning from interaction, existing deep RL approaches often lack explicit planning capabilities, leading to suboptimal performance. Specifically, portfolio management, a sequential decision-making problem, is challenging because it involves a vast state-action space and non-differentiable utility functions. This paper addresses the need for a more sophisticated planning mechanism within deep RL for portfolio management that can effectively navigate these complexities and optimize for financial objectives.

Methods

The core contribution is the A* Tree Search (ATS) algorithm. ATS merges the strengths of A* search (prioritizing optimal paths using heuristic evaluation) and Monte Carlo Tree Search (MCTS) (exploration and simulation).

  • A* Search Integration: Unlike standard MCTS which uses average information to guide its search, ATS incorporates the A* principle of using an optimal value to guide the search. This means it prioritizes exploring nodes that appear most promising based on a heuristic evaluation.
  • Enhanced Tree Structure: The paper proposes a "maximum tree structure" where parent nodes consider the maximum action value of their child nodes. This ensures that the greedy selection from the root node leads to the globally maximum action value.
  • Neural Network Integration: A deep neural network (DNN) is used to provide prior probabilities for actions and estimate state values. This DNN is trained using experiences gathered from the ATS.
  • Exploration and Pruning: ATS improves upon A* by incorporating exploration through an upper confidence bound (UCB) mechanism, similar to MCTS. It also leverages the DNN's prior probabilities to prune inferior branches of the search tree, making the search more efficient.
  • Portfolio Management Specifics: The framework is adapted for portfolio management by defining a discrete action space (portfolio board lots) and a path utility function based on the Sharpe ratio, which encourages exploration while penalizing downside risk.

Datasets

The paper uses simulated data and real-world market data for evaluation.

  • Simulated Data: Three artificial price series generated from log price series as random walks with autoregressive trend processes.
  • American Market Data: Daily closing prices of S&P 500, DJIA, and NASDAQ indices from Yahoo Finance (January 2017 to August 2018).
  • Hong Kong Market Data: Daily closing prices of Hang Seng Index (HSI), Hang Seng China-Affiliated Corporations Index (HSCCI), and Hang Seng China Enterprises Index (HSCEI) (January 1998 to December 1999).

Key Insights and Ideas

  • Bridging Search and RL: The paper successfully bridges the gap between traditional search algorithms (like A*) and deep reinforcement learning, demonstrating that combining explicit planning with learned policies can yield superior results.
  • Optimal Node Prioritization: The key insight is that for one-player problems like portfolio management, focusing on the optimal node (rather than the average) in the search tree is more effective for guiding decisions.
  • DNN as a Guiding Heuristic: The DNN's role extends beyond just outputting a policy; it acts as a crucial heuristic function, providing prior probabilities that significantly prune the search space and guide the A* search.
  • Discrete Actions for Real-World Applicability: By defining a discrete action space for portfolio management (board lots), the system addresses the practical challenge of converting continuous portfolio weights into executable trades.
  • Adaptive Learning: The system is designed to retrain the DNN in an adaptive style as new market data becomes available, allowing it to adjust to changing market conditions.

Key Results

The ATS algorithm demonstrated strong performance across various benchmarks:

  • Simulated Data: ATS achieved the highest profit gain compared to DDPG, DRL, and a Hold strategy. While DRL had a slightly better risk-adjusted return (SR), ATS's discrete action space led to some fluctuations.
  • American Market Data: ATS outperformed DDPG, DRL, and Hold across all three evaluation metrics (FRR, SR, DDR), achieving the best profit rate. The paper suggests ATS's ability to jump between local optima due to its discrete action space is an advantage.
  • Hong Kong Market Data: ATS again showed the best performance for FRR, SR, and DDR, even in a downward market trend, outperforming DDPG, DRL, Hold, and other specialized methods like APT-based and Return-based.

Limitations and Future Work

  • Discrete Action Space Limitations: The paper acknowledges that the discrete action space, while practical, can lead to fluctuations and may not achieve arbitrary weights as effectively as continuous methods. Future work could explore more delicate discretization or hybrid approaches.
  • Market Regularity: The authors note that stock market regularity can vary significantly. Future research could focus on incorporating more information to mitigate noise in price data and adapt to different market regimes.
  • Dimension Explosion: The paper mentions that discretizing action space can lead to dimension explosion. Future work might investigate methods to alleviate this problem.

Summary updated

BibTeX
@misc{xu2019tree,
  author = {Lei Xu},
  title = {{A* Tree Search for Portfolio Management}},
  year = {2019},
  eprint = {1901.01855},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1901.01855},
}
Figure