In this work we present a number of urn models in which, contrary to standard Polya urns, the number of competing alternatives is not given from the outset but may increase with the arrival of innovations. We begin by describing a variant of Polya urns, first introduced by Fred Hoppe, in which balls of previously non existing colours are added with some (declining) probability. We then propose new variants in which the probability of the arrival on new colours is itself subject to adaptive change depending on the success of past innovations. We numerically simulate different specifications of these urns with adaptively changing mutation rate and show that they can account for complex patterns of evolution in which periods of exploration with clusters of innovations are followed by periods in which the dynamics of the system is driven by selection among a stable set of alternatives.