The need for efficient image browsing and searching motivates the use of Content-Based Image Retrieval (CBIR) systems. However, they suffer from a big gap between high-level image semantics and low-level features. So, a learning process to reduce the gap seems quite useful. This paper presents a novel Learning Automata (LA)-based approach to improve the CBIR systems. Distributed Learning Automata (DLA) is used in this work to learn the relevant images from textual query feedbacks of the users. Subsequently, the retrieved images are ranked according to the learning outcome and similarity measure In this study, the similarity between images is evaluated based on two color descriptors: the global color histogram and local color auto-correlogram. A thorough observation and comparison of these color descriptors performances are performed with different color spaces and also with various similarity measures. Experimental results on two publicly available databases demonstrate that the performance of the proposed CBIR system after each round is improved and the system could retrieve images compatible with the users’ perception.