Millimeter-wave (mmWave) backhauling is key to ultra-dense deployments in beyond-5G networks because providing every base station with a dedicated fiber-optic backhaul link to the core network is technically too complicated and economically too costly. Self-backhauling allows the operators to provide fiber connectivity only to a small subset of base stations (Fiber-BSs), whereas the rest of the base stations reach the core network via a (multi-hop) wireless link towards the Fiber-BS. Although a very attractive architecture, self-backhauling is proven to be an NP-hard route selection and resource allocation problem. The existing self-backhauling solutions lack practicality because: (i) they require solving a fairly complex combinatorial problem every time there is a change in the network (e.g., channel fluctuations), or (ii) they ignore the impact of network dynamics which are inherent to mobile networks. In this article, we propose SCAROS which is a semi-distributed learning algorithm that aims at minimizing the end-to-end latency as well as enhancing the robustness against network dynamics including load imbalance, channel variations, and link failures. We benchmark SCAROS against state-of-the-art approaches under a real-world deployment scenario in Manhattan and using realistic beam patterns obtained from off-the-shelf mmWave devices. The evaluation demonstrates that SCAROS achieves the lowest latency, at least 1.8 × higher throughput, and the highest flexibility against variability or link failures in the system.