Controlling antenna tilts in cellular networks is critical to achieve a good trade-off between network coverage and capacity. We devise algorithms learning optimal tilt control policies from existing data (passive learning setting) or from data actively generated by the algorithms (active learning setting). We formalize the design of such algorithms as a Best Policy Identification problem in Contextual Linear Bandits (CLB). In CLB, an action represents an antenna tilt update; the context captures current network conditions; the reward corresponds to an improvement of performance, mixing coverage and capacity. The objective is to identify an approximately optimal policy (a function mapping the context to an action with maximal reward). For both active and passive learning, we derive information-theoretical lower bounds on the number of samples required by any algorithm returning an approximately optimal policy with a given level of certainty, and devise algorithms achieving these fundamental limits. We apply our algorithms to the Remote Electrical Tilt optimization problem in cellular networks, and show that they can produce optimal tilt update policy using much fewer data samples than naive or existing rule-based learning algorithms. This paper is an extension of work presented at IEEE International Conference on Computer Communications (INFOCOM) 2022 (Vannella et al. 2022).