Much previous research has investigated explicit, machine-processable norms as a means to facilitate coordination in open multi-agent systems. This research can typically be classified as considering either offline design (norms are synthesised at design time) or online design. Online synthesis techniques aim to construct norms for a system while that system is actually running. A promising recent approach to on-line norm synthesis has been proposed but it suffers from serious drawbacks: (i) it needs too much nformation; (ii) it ignores issues of compactness in terms of minimality (ensuring that norms are not superfluous) and simplicity (ensuring that agents can process norms with little computational effort). To overcome these drawbacks, we propose an optimistic approach which, even though it uses less information, is able to explore more norms and synthesises sets of norms which are more compact. We present experimental evidence of the quality of our approach.