In a dynamic environment, some services may become unavailable, some new services may be published and the various properties of the services, such as their prices and performance, may change. Thus, to ensure user satisfaction in the long run, it is desirable that a service composition can automatically adapt to these changes. To this end, we leverage the technology of reinforcement learning and propose a mechanism for adaptive service composition. The mechanism requires no prior knowledge about services' quality, while being able to achieve the optimal composition solution. In addition, it allows a composite service to dynamically adjust itself to fit a varying environment. We present the design of our mechanism, and demonstrate its effectiveness through an extensive experimental evaluation.