In geophysical data assimilation, the control space is by definition the set of parameters which are estimated through the assimilation of observations. It has recently been proposed to design the discretizations of control space in order to assimilate observations optimally. The present paper describes the embedding of that formalism in a consistent Bayesian framework. General background errors are now accounted for. Scale-dependent errors, such as aggregation errors (that lead to representativeness errors) are consistently introduced. The optimal adaptive discretizations of control space minimize a criterion on a dictionary of grids. New criteria are proposed: degrees of freedom for the signal (DFS) built on the averaging kernel operator, and an observation-dependent criterion. These concepts and results are applied to atmospheric transport of pollutants. The algorithms are tested on the European tracer experiment (ETEX), and on a prototype of CO2 flux inversion over Europe using a simplified CarboEurope-IP network. New types of adaptive discretization of control space are tested such as quaternary trees or factorised trees. Quaternary trees are proven to be both economical, in terms of storage and CPU time, and efficient on the test cases. This sets the path for the application of this methodology to high-dimensional and noisy geophysical systems. Part II of this article will develop asymptotic solutions for the design of control space representations that are obtained analytically and are contenders to exact numerical optimizations. Copyright © 2011 Royal Meteorological Society