One that hasn't been mentioned is the most prestigious and rarest of all military decorations; the Grass Crown. This crown would be presented to a military commander who rescued a Roman army from besiegement or a blockade. The crown would be made up of foliage from the battlefield like grasses, weeds, wheat, flowers etc. The army that was saved by the commander would vote to present the crown to the commander. Pliny speakes of it:
"But as for the crown of grass, it was never conferred except at a crisis of extreme desperation, never voted except by the acclamation of the whole army, and never to any one but to him who had been its preserver. Other crowns were awarded by the generals to the soldiers, this alone by the soldiers, and to the general. This crown is known also as the "obsidional" crown, from the circumstance of a beleaguered army being delivered, and so preserved from fearful disaster. If we are to regard as a glorious and a hallowed reward the civic crown, presented for preserving the life of a single citizen, and him, perhaps, of the very humblest rank, what, pray, ought to be thought of a whole army being saved, and indebted for its preservation to the valour of a single individual?"
Sulla was one of these generals who received a Grass Crown.
The Laurels were traditionally a symbol of victory, and in the time of the republic a general who won a brilliant victory was awarded a triumph, which entailed several lictors with their fasces adorned with laurels. They could not enter rome before their triumph. As was said, the Laurel Wreath dates back further, i'm not sure when.