REM Behavior Disorder (RBD) is a serious risk factor for neurodegenerative diseases such as Parkinson's disease (PD). In this paper we describe deep learning methods for RBD prognosis classification from electroencephalography (EEG). We work using a few minutes of eyes-closed resting state EEG data collected from idiopathic RBD patients (121) and healthy controls (HC, 91). At follow-up after the EEG acquisition (mean of 4 +/- years), a subset of the RBD patients eventually developed either PD (19) or Dementia with Lewy bodies (DLB, 12), while the rest remained idiopathic RBD. We describe first a deep convolutional neural network (DCNN) trained with stacked multi-channel spectrograms, treating the data as in audio or image problems where deep classifiers have proven highly successful exploiting compositional and translationally invariant features in the data. Using a multi-layer architecture combining filtering and pooling, the performance of a small DCNN network typically reaches 80% classification accuracy. In particular, in the HC vs PD-outcome problem using a single channel, we can obtain an area under the curve (AUC) of 87%. The trained classifier can also be used to generate synthetic spectrograms to study what aspects of the spectrogram are relevant to classification, highlighting the presence of theta bursts and a decrease of power in the alpha band in future PD or DLB patients. For comparison, we study a deep recurrent neural network using stacked long-short term memory network (LSTM) cells or gated-recurrent unit (GRU) cells, with similar results. We conclude that, despite the limitations in scope of this first study, deep classifiers may provide a key technology to analyze the EEG dynamics from relatively small datasets and deliver new biomarkers.