Edge computing has emerged as a powerful technology for enhancing the performance of on-device video analytics, which is critical to support real-time applications. Nevertheless, there still lack of effective metrics to guide the offloading decision of video analytics tasks between device and edge server. Additionally, these existing optimization mechanisms either presume prior knowledge of the ground-truth of previous inferences or involve high training overheads, thereby rendering them unsuitable for real-time situations. To address these challenges, this paper presents a system model of edge-assisted online video analytics, where a lightweight object tracking module and a complex DNN-based model are deployed at the device and edge server, respectively. We formulate the resolution and deviation-based offloading (RDO) problem by considering heterogeneous computation resources and dynamic network bandwidth, aiming at maximizing inference accuracy and processing rate concurrently. We propose a context-aware offloading (CO) algorithm based on Bayesian optimization, which learns the optimal parameter settings by evaluating reward based on Gaussian process. Notably, the CO is proved to offer near-optimal solution with sublinear regret. Finally, we build a testbed and test algorithm performance on three realistic video datasets. The simulation results illustrate that the proposed CO outperforms other existing solutions in various service scenarios.