We propose a learning-based robust predictive control algorithm that canhandle large uncertainty in the dynamics for a class of discrete-time systemsthat are nominally linear with an additive nonlinear dynamics component. Suchsystems commonly model the nonlinear effects of an unknown environment on anominal system. Motivated by an inability of existing learning-based predictivecontrol algorithms to achieve safety guarantees in the presence ofuncertainties of large magnitude in this setting, we achieve significantperformance improvements by optimizing over a novel class of nonlinear feedbackpolicies inspired by certainty equivalent "estimate-and-cancel" control lawspioneered in classical adaptive control. In contrast with previous work inrobust adaptive MPC, this allows us to take advantage of the structure in the apriori unknown dynamics that are learned online through function approximation.Our approach also extends typical nonlinear adaptive control methods to systemswith state and input constraints even when an additive uncertain functioncannot directly be canceled from the dynamics. Moreover, our approach allows usto apply contemporary statistical estimation techniques to certify the safetyof the system through persistent constraint satisfaction with high probability.We show that our method allows us to consider larger unknown terms in thedynamics than existing methods through simulated examples.