Users leaving your site could be a good thing as well as a bad thing. Undoing the damage will take some planning, endurance, and patience.
Good thing:
The policy change has caused members who are disruptive, violent, non-productive, and generally not good for the community to leave. If this was the point of your policy change then I commend you for a job well done! I suspect however, that this was not your intent.
Bad thing:
Lots of your good members are gone and have left the site with the non-productive, non-engaged users behind. Those who remained loyal may end up leaving because their friends left and it's just not the same anymore without them. These are not easy scenarios to recover from. Your site will likely never be the same again.
Possible Solutions:
These are not exhaustive, but given the limited information you provided, here are the roads you can follow.
(1) Move on with what you have. Rebuild with those who remained. You will need to engage users and make them the #1 priority. You will likely have to spend some money for prizes for the weekly or monthly contests you are going to run. You will need to post and create energetic discussions on your site as you seek to attract those who are not as active as the members who left. Now is the time to let your members vent as well. They will need to talk about what happened. Be prepared to handle some heated discussions. This is needed for healing and progress. Losing 50% of your traffic is no small thing. Be prepared to offer encouragement while remaining strong and decisive. If you have a team of moderators or staff, they will be crucial to helping the community overcome this event.
Depending on the size of the site, the genre, the history, and the vision of the community, recovery can take about a year. Be prepared for hard work and attention to the site. Pick your staff and your battles carefully. Yours is not the first community to go through a massive blow like this. Learn from your mistakes and improve!
(2) Retract your former position and restore things as they were. You can send out a newsletter to all members explaining the recent events and canceling the changes that were made. You will need to apologize and make better efforts of communicating with your members whenever big decisions like this are to be made.
Keep in mind that the damage has been done - you are not guaranteed to gain any members back. You risk losing your reputation as well. It seems to me that this was a poorly executed decision that was not discussed amongst the members prior to release. Remember that you are part of a community - lots of people are involved. People who join a community to be active are really giving much of themselves. You must respect that and try to do what is best for the community at all times and as much as possible.