The usual title is Ἱστορίαι, The Histories. The Rise of the Roman Empire is a title Penguin Classics used.

As for the rest of your question, you're confused on the definition of "empire." That's partly historians' fault. It is difficult to think of an empire without an emperor.

But an empire, in a political sense, just means one state is administering another without absorbing it. Until Augustus, provinces were technically theaters of war. The communities there had their own governments. Those governments were expected to cooperate with Roman goals, pay taxes, provide troops, etc, but Rome didn't directly intervene in their politics, unless something went sideways. Or you had some incredibly corrupt governor.

I will also note that Augustus was princeps, not emperor. Emperor is an English word derived from the Latin "imperator," which is just a title for a victorious general. Anyone acclaimed by the army during the Republican period could be imperator. One of the things Augustus did was constrict military honors to his family. He caused a scandal by blocking Crassus, the grandson of the famous Crassus from a triumph in 29. Crassus eventually got his triumph in 27, but to my knowledge, that was the last triumph celebrated outside the Julio-Claudian family until it died out. The Flavians practiced the same policy of limiting military honors to the family, and so on for the rest of history.

Firstly, it seems that title is only used for the Penguin edition of Polybius' work, most others simply call it "Histories" (this is its name in Loeb, for example). Secondly, what counts as an empire is not defined just by whether the ruler is titled 'emperor', see for instance this comment by u/lcnielsen and this discussion by u/yodatsracist and others. The Romans themselves indeed called the territories they possessed imperium before the reign of Augustus, as u/bigfridge224 explains here

The English title of the Historiae by Polybius has been explained well by u/gynnis-scholasticus and u/LegalAction. However, the term "imperium" comes from the verb "imparare" which means "to rule" or "to give orders". During the Roman Republic, it was used to describe the power of a political position that an elected office holder could muster in his realm of influence that office gave him. It goes together with the word "potestas" which can be translated as "official authority". So the phrase would be that Aedil/Praetor/Consul/Dictator xy "held an imperium". To symbolize this imperium, a Roman official with the power of an imperium was accompanied by socalled "lictores", who carried the insignia of his power for all to see. The number of these varied, the more impportant the official office was, the more lictores marched with the person who held an imperium.

The imperium gave the official powers inside the city of Rome as well as outside the "pomerium" the traditional frontier of the Roman city. Outside of the city, the inhabitants of an imperium usually held military power. While the power of their office inside Rome ended after their term of office was over, their imperium outside of the Roman city could be prolonged until a successor was named. They would then have authority as a "pro praetore" or "pro consule" ("instead of").

During the development of Rome gaining more influence in Italy and the Medierranean the meaning of the phrase "imperium" shifted to a more military context. During the second war against Carthage with the winner Scipio Africanus who won over Hannibal this change began.

​

Literature:

Fred K. Drogula: Commanders and Command in the Roman Republic and Early Empire. University of North Carolina Press: Chapell Hill 2015, ISBN 978-1-4696-2126-5.

Frederik J. Vervaet: The High Command in the Roman Republic. The Principle of the „summum imperium auspiciumque“ from 509 to 19 BCE (= Historia. Einzelschriften. Bd. 232). Franz Steiner, Stuttgart 2014, ISBN 978-3-515-10630-6.