Software-defined networking is a recently emerging paradigm that decouples the control and data planes of computer networks. It allows for the implementation of application-specific routing algorithms, and the advantages that the SDN architecture enables can be used to enhance the performance of multimedia communication applications. In this paper, we propose an adaptive video streaming system with a learning-based approach, running over SDN. In the proposed video streaming system, we use a novel learning model to determine the optimal time to re-route the traffic flows and to change the bitrate of the video. The learning model aims to minimize the packet loss rate, quality changes and controller cost while adapting the flow routes and video quality. We have tested the performance of the learning-based approach by comparing it to traditional Internet routing and the greedy approach. The results show that the proposed system significantly outperforms the traditional Internet routing approach and the greedy approach in terms of quality of experience (QoE) and network cost under different network scenarios. (C) 2015 Elsevier B.V. All rights reserved.