I think with practice, he'll become less dependent on treats. Sully is still fairly dependent on treats when I work with his tricks, too. But I've gotten him to the point where I can hold a treat in my hand but not give it to him, and he'll still do his tricks. I'll only give him a treat for a perfect performance of one of the newer tricks.
Here's a neat site that helped me when I was teaching Sully a few things:
http://www.geocities.com/Heartland/P.../indexorg.html