Generator start-up is a pivotal step of transmission system self-healing after large-scale blackouts. Considering the uncertainty of initial power system situation after blackouts and line restoration during power system restoration, an online generator start-up algorithm based on Monte Carlo tree search (MCTS) and sparse autoencoder (SAE) is proposed for real-time decision making. First, an online decision support system and a generator start-up efficiency indicator involving the total generation capability and number of restored lines are proposed. Then, the SAE is deployed to learn the data relevant to generator start-up offline to establish a value network, which is used to rapidly estimate the optimal generator start-up efficiency indicator. Next, MCTS used for the online generator start-up is improved by the modified upper confidence bound apply to tree algorithm, move pruning technique, and value network. It is used to search the next line to be restored based on real-time situation. Finally, root parallelization computation is adopted and a decision-making method is proposed to improve the reliability of decision making. Simulation results of the New England 10-unit 39-bus power system and Western Shandong Power Grid of China demonstrate that the proposed algorithm can accomplish generator start-up step by step reliably.