Device-to-Device (D2D) communication helps in increasing the coverage range and throughput in millimeter Wave (mmWave) networks. The performance of the mmWave D2D communication mainly depends on selecting the best neighbor device through a process of Beamforming Training (BT). The process of BT involves pointing beams of multiple resolutions at different angles to select the best neighbor device in terms of link quality. While the sender exhaustively performs BT with all the neighbors in naive BT, the Reinforcement Learning (RL) based techniques, on the other hand, employ exploration/exploitation strategies to intelligently search for the best neighbor.The state-of-the-art RL algorithms typically yield sub-optimal performance, by trading-off computational tractability over optimality. Tractable optimal solving methods are therefore critical in improving the performance of neighbor selection through an intelligent BT process. To this end, this work studies the problem structure of the mmWave BT neighbor selection process formulated as a Multi-Armed Bandit (MAB) problem and provides a simple and scalable optimal method to select mmWave D2D neighbors with the objective of maximizing throughput performance. With extensive simulations, the efficacy of the proposed framework is demonstrated.