This paper addresses a fundamental limitation of previous random access protocols, their lack of latency performance guarantees. We consider K IoT transmitters competing for uplink resources and we design a fully distributed protocol for deciding how they access the medium. Specifically, each transmitter restricts decisions to a locally-generated dictionary of transmission patterns. At the beginning of a frame, pattern i is chosen with probability p ^I , and an online exponentiated gradient algorithm is used to adjust this probability distribution. The performance of the proposed scheme is showcased in simulations, where it is compared with a basline random access protocol. Simulation results show that (a) the proposed scheme achieves good latent throughput performance and low energy consumption, while (b) it outperforms by a big margin random transmissions.