chief dates from medieval times. The Oxford English Dictionary has several definitions for chief, but the one applicable to your case is:
a. The head of a body of men, of an organization, state, town, party,
office, etc.; foremost authority, leader, ruler
and the OED has a citation from 1297:
1297 R. Gloucester's Chron. (1724) 212 Þo þe Romeyns were wyþ out
chef, dyscomfortd hii were
And the next two citations, of which the second is actually intelligible:
1475 (▸?c1400) Apol. Lollard Doctr. (1842) 57 Wan any auerous or
couetous is canonizid..or maad cheef.
1483 Caxton in tr. J. de Voragine Golden Legende 399 She was made
abbesse and chyef of al the monasterye
From reading the entire entry for chief, one sees that chief was a word widely used in medieval times, in many ways. For example:
†8. The head town or city; the capital n.1 Obs.
1393 J. Gower Confessio Amantis III. 164 Whan Rome was the worldes
So I think the bandits could well call their chief, chief, and how they would have spelled it (chef, chefe, cheef, chief, chief) is irrelevant because they were probably illiterate.
Addendum: See also Etymonline, chief