Multi-cloud storage is recently a viable approach to solve the vendor lock-in, reliability, and security issues in cloud storage systems. As a key concern, data placement influences the cost and performance of storage services. Yet, in practice it remains challenging to address the huge solution space. Previous studies typically focus on constructing efficient data placement schemes based on the predicted pattern of workloads or assuming fully a-priori known network conditions. They cannot be easily applied in multi-cloud storage scenarios, which typically involve dynamic network conditions and time-varying workloads. To this end, we formulate the data placement optimization in a combinatorial multi-arm bandit (CMAB) perspective and solve it by learning placement strategy online. In contrast to a stationary setting where reward distributions are unknown but identical over time, we consider a realistic multi-cloud environment with non-stationary conditions, i.e., reward distributions change over time. To swiftly accommodate this, we propose an adaptive window combinatorial upper confidence bound based data placement (AW-CUCB-DP) scheme to reduce latency and cost. In AW-CUCB-DP, a simple and efficient change detector, i.e.,Page-Hinkley testwith forgetting mechanism (FM-PHT), is employed to enable variable-size sliding windows to handle both gradual and abrupt variations in network conditions or workloads. We establish that AW-CUCB-DP is asymptotically optimal in the non-stationary multi-cloud environment. Trace-driven experiments further verify that our scheme outperforms alternatives, especially in highly dynamic environments.