Network Function Virtualization (NFV) replaces physical middleboxes with elastic Virtual Network Functions (VNFs). Those VNFs need to be instantiated, and their resources dynamically scaled to meet application and traffic fluctuation requirements. Despite recent extensive research, deciding how to map virtual resources optimally to the underlying infrastructure remains practically a challenge. Existing approaches mostly assign fixed resources to each VNF instance, and transfer virtual flows using a single physical path, without prior knowledge of traffic patterns and available bandwidth. Such resource binding strategies lead to suboptimal physical link utilization. We advance the state of the art in this regard by presenting OctoMap, a system designed to support with learning theory any chain embedding algorithm. OctoMap utilizes a Convolution Neural Network for traffic prediction and provisioning, and a contextual multi-armed bandit algorithm to solve the online VNF chain embedding problem. We show the performance benefits of OctoMap with a trace-driven simulation campaign using publicly available datasets. In particular, we show how OctoMap reduces the costs of provisioning network services under node and link constraints, comparing different predictors and different multi-armed bandit policies.