In traditional multi-armed bandits (MAB), a standard assumption is that the mean rewards are constant across each arm, a simplification that can be restrictive in nature. In many real-world settings, the rewards exhibit a periodic pattern on which traditional MAB algorithms would fail. This paper addresses the problem of regret minimization when the mean rewards change periodically. To this end, we propose an approach that utilizes the Ramanujan periodicity transform to estimate the support of the periods efficiently and, furthermore, use this information to minimize regret.

Periodic signals admit sparse representations in nested periodic dictionaries (NPDs). While sparse recovery algorithms rooted in the theory of compressive sensing can successfully recover their underlying periods, existing recovery conditions derived for random dictionaries are of limited use in this context as they fail to explain the achievability results of said algorithms. In addition, provable achievability guarantees specific to NPDs have been heretofore lacking. In this paper, we derive exact recovery conditions for sparse periodic signals by leveraging prior information about the structure of NPDs. As instances of such dictionaries, we investigate the achievability conditions for the Farey and the Ramanujan Periodicity Transform dictionaries. Our numerical results demonstrate that the newly derived conditions can provide guarantees for exact recovery with the Farey dictionary, and in turn for exact period estimation, for large enough data lengths.

Repetitive visual stimuli induce periodic Visual Evoked Potentials (VEPs) in the brain that can be potentially identified in an EEG trace. The ability to distinguish frequencies and patterns due to different stimuli is the basis for brain computer interfaces (BCIs) used for communication and control of neurologically disabled patients. Since such responses are recorded in presence of high levels of noise from background brain processes, the detection task is rather challenging. In this work, we propose a detection approach for VEPs based on Ramanujan Periodicity Transform matrices (RPT), which have shown promise in detecting periodicities in data. Our results show that the RPT-based approach can outperform conventional spectral techniques and the state-of-the-art correlation analysis, and is more compatible with real-time BCIs which have to work with short duration EEG epochs. The proposed approach is fairly robust to unknown natural latencies in brain response.