Rewarding non combat solutions:

My suggestion for this idea is to give xp per encounter resolution, not by killing enemies.

So wether you kill or lie through it you get the same anount of xp. Killing afterwards wouldnt give xp since the encounter was already solved.

This is like the milestone but on smaller scale, so if you get to an encounter or not, your total xp will differ from play to play.