In recent years, wireless node density has increased rapidly, as more base stations, users, and machines coexist. Exploiting this node density, cooperative relaying has been deployed to improve connectivity throughout the network. Such a configuration, however, often demands relay scheduling, which comes with increased channel estimation and signaling overheads. To reduce these overheads, in this paper, we propose low-complexity relay scheduling mechanisms with the aid of a multi-armed bandit (MAB) framework. More specifically, this MAB framework is used for relay scheduling, based only on observing the acknowledgements/negative-acknow-ledgements (ACK/NACK) of packet transmissions. Hence, a bandit-based opportunistic relay selection (BB - ORS) mechanism is developed, recovering eventually the performance of classical opportunistic relay selection (0RS) when channel state information (CSI) is available without requiring any CSI. In addition, a distributed implementation of BB - ORS is presented, herein called d - BB - ORS, where distributed timers are used at the relays for relay selection, thus reducing the signaling overhead significantly. BB - ORS is compared to optimal scheduling with full CSI and the negligible performance gap is compensated by the low-complexity low-overhead implementation, while it surpasses the performance of ORS with outdated CSI.