Best way to do a distance fade-out?

The side of my map is a cliff with an ocean. Falling off is instant death. 

I thought if i increase the distance from the player to the map perimeter and use graded lighting to zero, it would look like a natural fade-out in the distance. I was wrong. Instead it just looks like a big, black wall : (

Any advice on a better way to achieve this effect?