When did cohors equitata milliaria come into existence?

[Nathan Ross]

When Paul was taken to Caesarea he was surrounded by 200 infantry, 70 horseman, 200 spearmen

The '200 spearmen' are actually dexiolaboi, an unclear term - it means men who carry something in their right hand! They're clearly different to the infantry (stratiotoi) though, so could be some kind of militia, or slingers, or light troops of some other kind.

Interestingly, it does seem possible that the Samarian cohorts 'inherited' by Rome from the army of Herod (and which probably formed the initial Roman garrison of the new province) were organised into units of 1000. Several of the Cohortes Sebastenorum - into which they in time evolved - were miliarian in later years.