In compressed sensing, a primary problem to solve is to reconstruct a high dimensional sparse signal from a small number of observations. In this work, we develop a new sparse signal recovery algorithm using reinforcement learning (RL) and Monte CarloTree Search (MCTS). Similarly to orthogonal matching pursuit (OMP), our RL+MCTS algorithm chooses the support of the signal sequentially. The key novelty is that the proposed algorithm learns how to choose the next support as opposed to following a pre-designed rule as in OMP. Empirical results are provided to demonstrate the superior performance of the proposed RL+MCTS algorithm over existing sparse signal recovery algorithms. We consider the compressed sensing (CS) problem [1; 2; 3] , where for a given matrix A ∈ R m×n , m n, and a (noiseless) observation vector y = Ax 0 , we want to recover a k-sparse vector/signal x 0 (k < m). Formally, it can be formulated as: subject to Ax = Ax 0 (2) Related work There is a large collection of algorithms for solving the CS problem. Some foundational and classic algorithms include convex relaxation, matching and subspace pursuit [4; 5; 6] and iterative thresholding [7; 8] . In particular, two well-established methods are (i) Orthogonal Matching Pursuit (OMP) and (ii) Basis Pursuit (BP). OMP recovers x 0 by choosing the columns of A iteratively until we choose k columns [9] . BP recovers x 0 by solving min Ax=y ||x|| 1 [2] . Because OMP and BP are extremely well studied theoretically [1; 2] and empirically [10] , we use these two algorithms as the main baseline methods to compare against when evaluating the proposed RL+MCTS algorithm. Recent advancements in machine learning have opened a new frontier for signal recovery algorithms. Specifically, these algorithms take a deep learning approach to CS and the related error correction problem. The works in [11] , [12] , [13] and [14] apply ANNs and RNNs for encoding and/or decoding of signals x 0 . Modern generative models such as Autoencoder, Variational Autoencoder, and Generative Adversarial Networks have also been used to tackle the CS problem with promising theoretical and empirical results [15; 16; 17] . These works involve using generative models for encoding structured signals, as well as for designing the measurement matrix A. Notably, the empirical results in these works typically use structured signals in x 0 . For example, in [16] and [17] , MNIST digits and celebrity images are used for training and testing. Our contribution Differently from the above learning-based works, our innovation with machine learning is on signal recovery algorithms (as opposed to signal encoding or measurement matrix design). We do not assume the signals to be structured (such as images), but cope with general sparse signals. This underlying model for x 0 is motivated by the same assumptions in the seminal work on universal phase transitions by Donoho and Tanner in [10] . Moreover, we assume the measurement matrix A is given. Extending to varying matrices A is left for future investigation. In this work, we approach the signal recovery problem using reinforcement learning (RL). Specifically, we leverage the Monte Carlo Tree Search (MCTS) technique with RL, which was shown to achieve outstanding performance in the game of Go [18; 19] . We further introduce special techniques to reduce the computational complexity for dealing with higher signal sparsity in CS. Experimental results show that the proposed RL+MCTS algorithm significantly outperforms OMP and BP for matrix A of various sizes. We have shown that the proposed RL+MCTS algorithm is a highly effective sparse signal decoder for the compressed sensing problem assuming no signal structure other than sparsity. Even without using MCTS in testing, the RL+MCTS algorithm's performance exceeds that of existing sparse signal recovery algorithms such as OMP and BP. The flexibility in the RL+MCTS algorithm's design further offers many interesting avenues for future research. For one, it is possible that the features chosen in our model can be further improved. Secondly, since the true signal x 0 is known in training, one may be able to leverage the information about x 0 to increase training sample efficiency. The training hyper-parameters may also be further tuned to improve performance. Broader settings of problems such as noisy observations and varying observation matrices A are under active investigation.
Formulating sparse signal recovery as a sequential decision making problem, we develop a method based on RL and MCTS that learns a policy to discover the support of the sparse signal. 
{"src": "scitldr-AIC_train", "paper_id": "Sygfa739LS"}