late 14c., "person who has power of judging absolutely according to his own pleasure in a dispute or issue," from Old French arbitre "arbiter, judge" (13c.) and directly from Latin arbiter "one who goes somewhere (as witness or judge)," in classical Latin used of spectators and eye-witnesses; specifically in law, "he who hears and decides a case, a judge, umpire, mediator;" from ad "to" (see ad-) + baetere "to come, go," a word of unknown etymology.
The attestations suggest that baetō was the original form which sometimes became bētō, while -bītō was regular in non-initial syllables (especially in Plautus). Where bītō occurs independently (4x in Plautus), it must be a decompounded form. [de Vaan]
The specific sense of "one chosen by two disputing parties to decide the matter" is from 1540s. Compare arbitrator. The earliest form of the word attested in English is the fem. noun arbitress (mid-14c.) "a woman who settles disputes." Gaius Petronius Arbiter (circa 27-66 C.E.) was a friend of Nero, noted voluptuary, reputed author of the "Satyricon," and an authority on matters of taste and style (elegantiae arbiter, punning on the name).