Grant an experience level or two for completing Sokoban without penalties (or with an acceptably small number of penalties). Also maybe a permanent +1 luck that never decays, like with a full moon. Possibly remove the rings and wands or the prize to compensate, since they make the branch effectively non-optional and it should be optional.