This paper presents an online framework for synthesizing agile locomotion for bipedal robots that adapts to unknown environments, modeling errors, and external disturbances. To this end, we leverage step-to-step (S2S) dynamics which has proven effective in realizing dynamic walking on underactuated robots -- assuming known dynamics and environments. This paper considers the case of uncertain models and environments and presents a data-driven representation of the S2S dynamics that can be learned via an adaptive control approach that is both data-efficient and easy to implement. The learned S2S controller generates desired discrete foot placement, which is then realized on the full-order dynamics of the bipedal robot by tracking desired outputs synthesized from the given foot placement. The benefits of the proposed approach are twofold. First, it improves the ability of the robot to walk at a given desired velocity when compared to the non-adaptive baseline controller. Second, the data-driven approach enables stable and agile locomotion under the effect of various unknown disturbances: additional unmodeled payload, large robot model errors, external disturbance forces, biased velocity estimation, and sloped terrains. This is demonstrated through in-depth evaluation with a high-fidelity simulation of the bipedal robot Cassie subject to the aforementioned disturbances.