You can get a marker with even a one-unit-vs-one-unit battle if you kill all the enemy for no losses. It doesn't have to be a massive fight.

I get them all the while when rebel hunting with since I primarily use archers for that, rarely having to use my line infantry or cavalry except for skewering routers.